A Robust And Efficient Proposal For Solving The Linear Systems Arising In Interior-Point Methods For Linear Programming

The computational burden of primal-dual interior point methods for linear program-ming relies on the computation of the search direction by solving one or more linear systems per iterations. The objective of this work is to study an efficient and robust way of solving these systems for large-scale sparse problems. Our proposal combines the use of the stable system and a hybrid iterative method where a conjugate gradient method is preconditioned during the initial interior point iterations by an incomplete Cholesky factorization type. The linear systems arising at each iteration of an interior point method are indefinite and they can be written in a symmetric form, which is known as augmented system. A common approach in interior point solvers for linear programming reduces the augmented system to a smaller positive definite one, called normal equations system and the search direction is found by solving the smaller system. This latter approach suffers from some numerical drawbacks. The normal equations system matrix can be dense (even if the original constraint matrix A is sparse) when A has dense columns. Furthermore, even A being sparse the Cholesky factors may be dense. These features need to be appropriatel