Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Technical Report MS 02-002

L. Bergamaschi, J. Gondzio, G. Zilli

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than that used in a direct approach they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are bounded away from zero. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.

Key words: Interior-point methods, Iterative solvers, Preconditioners.

Written: July 26, 2002, revised March 18, 2003 and August 29, 2003.
Published: Computational Optimization and Applications vol 28 (2004) No 2, pp. 149-171.
Received the 2004 COAP Best Paper Award.

Related Software:
HOPDM Higher Order Primal Dual Method.