Interior-point methods for linear and convex quadratic programming
require the solution of a sequence of symmetric indefinite linear
systems which are used to derive search directions. Safeguards are
typically required in order to handle free variables or rank-deficient
Jacobians. We propose a consistent framework and accompanying
theoretical justification for regularizing these linear systems. Our
approach is akin to the proximal method of multipliers and can be
interpreted as a simultaneous proximal-point regularization of the
primal and dual problems. The regularization is termed "exact" to
emphasize that, although the problems are regularized, the algorithm
recovers a solution of the original problem. Numerical results will be
presented. If time permits we will illustrate current research on a
matrix-free implementation.
This is joint work with Michael Friedlander, University of British Columbia, Canada