Preconditioners for Indefinite Systems Arising in Optimization

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 = UT 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 UT 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² AT Δ π = r when the latter become excessively ill conditioned.