Preconditioning indefinite systems in interior point methods for optimization

L. Bergamaschi, G. Zilli, J. Gondzio

Research output: Contribution to journalArticlepeer-review

Abstract

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 preconditioned which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches 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 strictly positive. 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.
Original languageEnglish
Pages (from-to)149-171
Number of pages23
JournalComputational optimization and applications
Volume28
Issue number2
DOIs
Publication statusPublished - 1 Jul 2004

Fingerprint

Dive into the research topics of 'Preconditioning indefinite systems in interior point methods for optimization'. Together they form a unique fingerprint.

Cite this