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.