L. Bergamaschi, J. Gondzio, G. Zilli
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 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.