Final Iterations in Interior Point Models -- Preconditioned Conjugate Gradients and Modified Search Directions

Abstract

In this article we consider modified search directions in the endgame of interior point methods for linear programming. In this stage, the normal equations determining the search directions become ill-conditioned. The modified search directions are computered by solving perturbed systems in which the systems may be solved efficiently by the preconditioned conjugate gradient solver. We prove the convergence of the interior point methods using the modified search directions and show that each barrier problem is solved with a superlinear convergence rate. A variation of Cholesky factorization is presented for computing a better preconditioner when the normal equations are ill-conditioned. These ideas have been implemented successfully and the numerical results show that the algorithms enhance the performance of the preconditioned conjugate gradients-based interior point methods.