《《2016 Preconditioning Indefinite Systems in Interior Point Methods for Optimization》.pdf

Computational Optimization and Applications, 28, 149–171, 2004 c 2004 Kluwer Academic Publishers. Manufactured in The Netherlands. Preconditioning Indefinite Systems in Interior Point Methods for Optimization LUCA BERGAMASCHI berga@dmsa.unipd.it Department of Mathematical Methods for Applied Sciences, University of Padua, Italy JACEK GONDZIO J.Gondzio@ed.ac.uk School of Mathematics, University of Edinburgh, Scotland GIOVANNI ZILLI zilli@dmsa.unipd.it Department of Mathematical Methods for Applied Sciences, University of Padua, Italy Received August 8, 2002; Revised September 8, 2003 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 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