Computational Experience with a Preconditioner for Interior Point Methods for Linear Programming

A. R. L. Oliveira and D. C. Sorensen

In this paper, we discuss efficient implementation of a new class of preconditioners for linear systems arising from interior point methods. These new preconditioners give superior performance near the solution of a linear programming problem where the linear systems are typically highly ill-conditioned. They rely upon the computation of an $LU$ factorization of a subset of columns of the matrix of constraints. The implementation of these new techniques require some sophistication since the subset of selected columns is not known a priori. The conjugate gradient method using this new preconditioner compares favorably with the Cholesky factorization approach. The new approach is clearly superior for large scale problems where the Cholesky factorization produces intractable fill-in. Numerical experiments on several representative classes of linear programming problems are presented to demonstrate the promise of the new preconditioner.

Technical Report TR97-28, Department of Computational and Applied Mathematics, Rice University, Houston TX, November 1997.