STABILITY OF LINEAR-EQUATIONS SOLVERS IN INTERIOR-POINT METHODS

Primal-dual interior-point methods for linear complementarity and line ar programming problems solve a linear system of equations to obtain a modified Newton step at each iteration. These linear systems become i ncreasingly ill-conditioned in the later stages of the algorithm, but the computed steps are often sufficiently accurate to be useful. We us e error analysis techniques tailored to the special structure of these linear systems to explain this observation and examine how theoretica lly superlinear convergence of a path-following algorithm is affected by the roundoff errors.