Stable Reduction to KKT Systems in Barrier Methods for Linear and Quadratic Programming

We discuss methods for solving the key linear equations within primal-dual barrier methods for linear and quadratic programming. Following Freund and Jarre, we explore methods for reducing the Newton equations to 2 x 2 block systems (KKT systems) in a stable manner. Some methods require partitioning the variables into two or more parts, but a simpler approach is derived and recommended. To justify symmetrizing the KKT systems, we assume the use of a sparse solver whose numerical properties are independent of row and column scaling. In particular, we regularize the problem and use indefinite Cholesky-type factorizations. An implementation within OSL is tested on the larger NETLIB examples.