Preconditioners for indefinite systems arising in optimization.

*(English)*Zbl 0749.65037Authors’ 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.

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.

Reviewer: S.Grzegorski (Lublin)

##### MSC:

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 |