zbMATH — the first resource for mathematics

Preconditioners for indefinite systems arising in optimization. (English) Zbl 0749.65037
Authors’ summary: 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^ TDU\), 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^ TDU\) 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 (Karush-Kuhn-Tucker)-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^ 2A^ T\Delta\pi=r\) when the latter become excessively ill conditioned.

65K05 Numerical mathematical programming methods
65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling
90C30 Nonlinear programming
90C05 Linear programming
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
Full Text: DOI