ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

15. Numerical Analysis and Scientific Computing

1991 MS Classification: 65 Numerical Analysis Wang, Weichung, National Tainan Teachers College, Taiwan Using Preconditioned Conjugate Gradients in Final Iterations of Interior Point Methods 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. 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. 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.