Regularized Symmetric Indefinite Systems in Interior Point Methods for Linear and Quadratic Optimization

Logilab Technical Report 1998.6

A. Altman and J. Gondzio

This paper presents linear algebra techniques used in the implementation of an interior point method for solving linear programs and convex quadratic programs with linear constraints. New regularization techniques for Newton systems applicable to both symmetric positive definite and symmetric indefinite systems are described. They transform the latter to quasidefinite systems known to be strongly factorizable to a form of Cholesky-like factorization. Two different regularization techniques, primal and dual, are very well suited to the (infeasible) primal-dual interior point algorithm. This particular algorithm, with an extension of multiple centrality correctors, is implemented in our solver HOPDM . Computational results are given to illustrate the potential advantages of the approach when applied to the solution of very large linear and convex quadratic programs.

Key words: Linear Programming, Convex Quadratic Programming, Symmetric Quasidefinite Systems, Primal-Dual Regularization, Primal-Dual Interior Point Method, Multiple Centrality Correctors.

PDF TR1998.6.pdf.
Written: March 1998, revised November 1998 and February 1999.
Published: Optimization Methods and Software 11-12(1999) 275-302.