Preconditioning primal-dual interior point methods for linear programming

Timothy Rees
Dept. of Computer Science
University of British Columbia, Vancouver BC CANADA V6T 1Z4
trees@cs.ubc.ca
Chen Greif

We investigate the application of a class of preconditioners to the problem of solving the linear systems arising from primal-dual interior point methods in linear and quadratic programming. The preconditioners have the attractive property of improved eigenvalue clustering with increased singularity of the (1,1) block of the saddle-point matrix. We analyze spectral properties of the preconditioned matrix utilizing projections onto the null space of the constraint matrix. We then present a practical application of the preconditioners and study their performance on LP and QP problems from the NETLIB and QPS test suites.