Regularized Symmetric Indefinite Systems in Interior Point Methods
for Linear and Quadratic Optimization
Anna Altman and Jacek 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. The new regularization
techniques for Newton equation system 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 {\it primal} and {\it dual}
suit very well 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 applied to the solution of very large linear and convex
quadratic programs.
Logilab Technical Report 98.6,
Section of Management Studies, University of Geneva,
102 Bd Carl Vogt, CH-1211 Geneva 4, Switzerland,
March 1998.
Contact: [email protected]