(251c) Domain Decomposition Preconditioners for Schur Complement Systems Arising in Structured Nonlinear Optimization Problems

Modern engineering challenges, such as the design and operation of integrated energy systems, enterprise-wide optimization, or infectious disease modelling, define increasingly complex and large-scale optimization problems. In part, this is due to structural changes of some applications, such as the integration of renewable energy sources into the electric grid or the globalized nature of supply chains. However, continuous improvements of both computing architectures and optimization algorithms also enable practitioners to consider problems previously deemed intractable.

Constrained, nonconvex, nonlinear optimization problems (NLPs) are usually solved using filter line-search interior point methods (IPMs), which involve the factorization of sparse, indefinite linear systems at every iteration [1], an operation which is not inherently parallelizable. Thus, the use of modern, highly parallel computing architectures for this class of algorithms has proved difficult in the past. Several recent works have made great progress on this front, for example by relaxing inequality constraints [2] or applying variations of the augmented Lagrangian approach [4,5]. These approaches are a significant step towards the parallel solution of general NLPs, yet the authors believe that the investigation of problem-specific parallel decomposition schemes remains an important part of tackling large-scale problems.

In this work, we focus on decomposition strategies for large-scale nonlinear optimization problems with spatial structure. Schur complement approaches can be employed to decompose the linear systems arising at every iteration of the interior point method. Thereby, the Schur complement system is solved implicitly using an iterative algorithm such as preconditioned gradient descent [6]. The performance of these methods greatly depends on the quality of the preconditioner, which is often designed for specific problem structures, e. g. stochastic programming [7, 8], distributed energy systems [9] or PDE-constrained optimization problems [10]. Decomposing on the linear algebra level within the IPM, as opposed to problem-level decompositions with penalty-type consensus updates [11,12], promises to maintain the favorable convergence properties of the outer algorithm. This must be weighed against the cost of applying an inner iterative scheme to often highly ill-conditioned Schur complement systems arising from the optimality conditions of the optimization problem. Furthermore, for non-convex problems, requirements on the inertia of the linear system must be enforced at every iteration. We discuss the use of domain decomposition preconditioners based on approaches from the PDE literature for Schur complement systems arising in optimization problems with spatial structure and evaluate the parallel performance on a set of dynamic parameter estimation problems from the field of infectious disease modelling.

References

[1] Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming, 106, 25-57.

[2] Shin, S., Pacaud, F., & Anitescu, M. (2023). Accelerating optimal power flow with gpus: Simd abstraction of nonlinear programs and condensed-space interior-point methods. arXiv preprint arXiv:2307.16830.

[4] Cao, Y., Seth, A., & Laird, C. D. (2016). An augmented Lagrangian interior-point approach for large-scale NLP problems on graphics processing units. Computers & Chemical Engineering, 85, 76-83.

[5] Regev, S., Chiang, N. Y., Darve, E., Petra, C. G., Saunders, M. A., Świrydowicz, K., & Peleš, S. (2023). HyKKT: a hybrid direct-iterative method for solving KKT linear systems. Optimization Methods and Software, 38(2), 332-355.

[6] Kang, J., Cao, Y., Word, D. P., & Laird, C. D. (2014). An interior-point method for efficient solution of block-structured NLP problems using an implicit Schur-complement decomposition. Computers & Chemical Engineering, 71, 563-573.

[7] Petra, C. G., & Anitescu, M. (2012). A preconditioning technique for Schur complement systems arising in stochastic optimization. Computational Optimization and Applications, 52, 315-344.

[8] Petra, C. G., Schenk, O., Lubin, M., & Gärtner, K. (2014). An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM Journal on Scientific Computing, 36(2), C139-C162.

[9] Rehfeldt, D., Hobbie, H., Schönheit, D., Koch, T., Möst, D., & Gleixner, A. (2022). A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models. European Journal of Operational Research, 296(1), 60-71.

[10] Heinkenschloss, M., & Nguyen, H. (2005). Balancing Neumann-Neumann methods for elliptic optimal control problems. In Domain decomposition methods in science and engineering (pp. 589-596). Berlin, Heidelberg: Springer Berlin Heidelberg.

[11] Knueven, B., Mildebrath, D., Muir, C., Siirola, J. D., Watson, J. P., & Woodruff, D. L. (2023). A parallel hub-and-spoke system for large-scale scenario-based optimization under uncertainty. Mathematical Programming Computation, 15(4), 591-619.

[12] Shin, S., Zavala, V. M., & Anitescu, M. (2020). Decentralized schemes with overlap for solving graph-structured optimization problems. IEEE Transactions on Control of Network Systems, 7(3), 1225-1236.