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: [email protected].
com