Final Iterations in Interior Point Models -- Preconditioned Conjugate
Gradients and Modified Search Directions
Final Iterations in Interior Point Models -- Preconditioned Conjugate
Gradients and Modified Search Directions
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Wang, Weichung
Advisor
Citation
DRUM DOI
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.