Preconditioners for Indefinite Systems Arising in Optimization
Philip E. Gill, Walter Murray, Dulce B. Ponceleón, Michael A. Saunders · SIAM Journal on Matrix Analysis and Applications · 1992
Methods are discussed for the solution of sparse linear equations $Ky = z$, where K is symmetric and indefinite. Since exact solutions are not always required, direct and iterative methods are both of interest. An important direct method is the Bunch–Parlett factorization $K = U^T DU$, where U is triangular and D is block-diagonal. A sparse implementation exists in the form of the Harwell code MA27. An appropriate iterative method is the conjugate-gradient–like algorithm SYMMLQ, which solves indefinite systems with the aid of a positive-definite preconditioner. For any indefinite matrix K, it is shown that the $U^T DU$ factorization can be modified at nominal cost to provide an “exact” preconditioner for SYMMLQ. Code is given for overwriting the block-diagonal matrix D produced by MA27. The KKT systems arising in barrier methods for linear and nonlinear programming are studied, and preconditioners for use with SYMMLQ are derived. For nonlinear programs a preconditioner is derived from the “smaller” KKT system associated with variables that are not near a bound. For linear programs several preconditioners are proposed, based on a square nonsingular matrix B that is analogous to the basis matrix in the simplex method. The aim is to facilitate solution of full KKT systems rather than equations of the form $AD^2 A^T \Delta \pi = r$ when the latter become excessively ill conditioned.