A New Class of Preconditioners for Large-Scale Linear Systems from Interior Point Methods for Linear Programming

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

A new class of preconditioners is proposed for the iterative solution of linear systems arising from interior point methods. In many cases, these linear systems are symmetric and indefinite. Typically, these indefinite systems can be reduced to an equivalent Schur complement system which is positive definite. We show that all preconditioners for the Schur complement system have an equivalent for the augmented system while the opposite is not true. This suggests it may be better to work with the augmented system. We develop some theoretical properties of the new preconditioners to support this. Computationally, we have verified that this class works better near a solution of the linear programming problem when the linear systems are highly ill-conditioned. Preliminary experiments which illustrate these features are presented. The techniques developed for a competitive implementation are presented in a follow up paper along with numerical experiments on several classes of linear programming problems.

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

Contact: aurelio@densis.fee.unicamp.br