Convergence of a Class of Inexact Interior-Point Algorithms for Linear Programs

Roland W. Freund, Florian Jarre, Shinji Mizuno

We present a convergence analysis for a class of inexact infeasible-interior-point methods for solving linear programs. The main feature of inexact methods is that the linear systems defining the search direction at each interior-point iteration need not be solved to high accuracy. More precisely, we allow that these linear systems are only solved to a moderate accuracy in the residual, but no assumptions are made on the accuracy of the search direction in the search space. In particular, our analysis does not require that feasibility is maintained even if the initial iterate happened to be a feasible solution of the linear program. We also present a few numerical examples to illustrate the effect of using inexact search direction on the number of interior-point iterations.

Numerical Analysis Manuscript 97--3--11, Bell Laboratories, Murray Hill, New Jersey.

Contact: freund@research.bell-labs. com