Preconditioning Indefinite Systems
in Interior Point Methods
for Large Scale Linear Optimization

Technical Report MS 2006-003

G. Al-Jeiroudi, J. Gondzio and J.A.J. Hall

We discuss the use of preconditioned conjugate gradients method for solving the reduced KKT systems arising in interior point algorithms for linear programming. The (indefinite) augmented system form of this linear system has a number of advantages, notably a higher degree of sparsity than the (positive definite) normal equations form. Therefore we use the conjugate gradients method to solve the augmented system and look for a suitable preconditioner.
An explicit null space representation of linear constraints is constructed by using a nonsingular basis matrix identified from an estimate of the optimal partition in the linear program. This is achieved by means of recently developed efficient basis matrix factorisation techniques which exploit hyper-sparsity and are used in implementations of the revised simplex method.
The approach has been implemented within the HOPDM interior point solver and applied to medium and large-scale problems from public domain test collections. Computational experience is encouraging.

Key words: Interior Point Methods, Linear Programming,
Preconditioned Conjugate Gradients, Indefinite System.

Written: June 12, 2006, revised February 23, 2007 and June 1, 2007.
Optimization Methods and Software 23 (2008) No 3, pp. 345-363.
Related Software:
HOPDM Higher Order Primal Dual Method.