Preconditioners for Indefinite Systems Arising in Optimization

We discuss 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 sub 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, we show that the U sub T DU factorization can be modified at nominal cost to provide an exact preconditioner for SYMMLQ. We give code for overwriting the block-diagonal matrix D produced by MA27. We then study the KKT systems arising in barrier methods for linear and nonlinear programming, and derive preconditioners for use with SYMMLQ. For nonlinear programs we suggest a preconditioner based on the smaller KKT system associated with variables that are not near a bound. For linear programs we propose several preconditioners 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 squared A sub T sub delta pi = r when the latter become excessively ill-conditioned. (kr).