Final iterations in interior point methods - Preconditioned conjugate gradients and modified search directions
Journal
Journal of the Australian Mathematical Society Series B-Applied Mathematics
Journal Volume
41
Journal Issue
3
Pages
312-328
Date Issued
2000
Author(s)
Wang, W.
Abstract
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 computed by solving perturbed systems in which the systems may be solved efficiently by the preconditioned conjugate gradient solver. 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.
Type
journal article