A. Altman and J. Gondzio
Abstract
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.