Solving reduced KKT systems in barrier methods for linear and quadratic programming

In barrier methods for constrained optimization, the main work lies in solving large linear systems $Kp = r$, where $K$ is symmetric and indefinite.

For linear programs, these KKT systems are usually reduced to smaller positive-definite systems $A^TH^{-1}A q = s$, where $H$ is a large principal submatrix of $K$. These systems can be solved more efficiently, but $A^TH^{-1}A$ is typically more ill-conditioned than $K$.

In order to improve the numerical properties of barrier implementations, we discuss the use of ``reduced KKT systems", whose dimension and condition lie somewhere in between those of $K$ and $A^TH^{-1}A. The approach applies to linear programs and to positive semidefinite quadratic programs whose Hessian $H$ is at least partially diagonal.

We have implemented reduced KKT systems in a primal-dual algorithm for linear programming, based on the sparse indefinite solver \MA27 from the Harwell Subroutine Library. Some features of the algorithm are presented, along with results on the Netlib LP test set.

Return To PEG's Home Page.