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.
Contact: [email protected]