(194a) Admm Preconditioning for Block-Structured Linear Algebra Systems

The scalability of optimization solvers relies quite heavily on the solution of the underlying linear algebra systems. Advances in direct sparse linear algebra solvers have been instrumental in the widespread use of nonlinear programming solvers. The success of interior point algorithms, for instance, can be in large part attributed to the development of direct and iterative linear solvers (1-4).

Specialized direct solution techniques have been developed to tackle large-scale and block-structured linear algebra systems (5-6) . Block structures appear in many important applications such as stochastic programming, network optimization, and optimal control (7). To exploit knowledge of the structure of these systems, Schur-complement decomposition techniques that leverage parallel computing architectures have been implemented to solve problems with millions of variables and constraints. Unfortunately, Schur-complement decomposition does not scale well in problems that exhibit a high degree of block coupling. The main reason for this is that assembling and factorizing the Schur-complement matrix is computationally expensive in such problems.

Iterative solution techniques and associated preconditioning strategies have been proposed to address fundamental scalability issues of direct solution strategies. In the context of block-structured problems, attempts have been made to solve the Schur complement system using iterative solution techniques. Unfortunately, preconditioning strategies for general problem classes are still lacking. Recently, it has been proposed to use ADMM as a preconditioner for Krylov-based iterative solvers such as GMRES (8-9). In this work, we test the performance of a ADMM-GMRES method in the context of block-structured linear systems. We demonstrate that this approach overcomes scalability issues of Schur-complement decomposition. We also show that ADMM-GMRES is significantly more effective than directly applying ADMM to solve the block-structured problem. The effectiveness of the approach is demonstrated using linear systems that arise in stochastic optimal power flow problems that contain up to 2 million variables and 4,000 coupling variables.

References

(1) J. Gondzio and A. Grothey. Exploiting structure in parallel implementation of interior point methods for optimization. Computational Management Science, 6(2):135–160, May 2009.

(2) Michele Benzi, Gene H. Golub, and Jrg Liesen. Numerical solution of saddle point problems. Acta Numerica, 14:1–137, 2005.

(3) Gene H. Golub and Chen Greif. On solving block-structured indefinite linear systems. SIAM Journal on Scientific Computing, 24(6):2076–2092, 2003.

(4) Philip E. Gill, Walter Murray, Dulce B. Poncelen, and Michael A. Saunders. Preconditioners for indefinite systems arising in optimization. SIAM Journal on Matrix Analysis and Applications, 13(1):292–311, 1992.

(5) Yankai Cao, Carl Laird, and Victor Zavala. Clustering-based preconditioning for stochastic pro- grams. Computational Optimization and Applications, 64(2):379–406, 2016.

(6) Jia Kang, Yankai Cao, Daniel P. Word, and C. D. Laird. An interior-point method for efficient solution of block-structured NLP problems using an implicit Schur-complement decomposition. Computers and Chemical Engineering, 71:563–573, 2014.