Stability of Augmented System Factorizations in Interior-Point Methods
Some implementations of
interior-point algorithms obtain their search directions by
solving symmetric indefinite systems of linear equations.
The conditioning of the coefficient matrices in these
so-called augmented systems deteriorates on later iterations,
as some of the diagonal elements grow without bound.
Despite this apparent difficulty, the steps
produced by standard factorization procedures
are often accurate enough to allow the interior-point method
to converge to high accuracy.
When the underlying linear program is nondegenerate,
we show that convergence to arbitrarily high accuracy
occurs, at a rate that closely approximates the theory.
We also explain and demonstrate what happens when
the linear program is degenerate, where convergence to
acceptable accuracy (but not arbitrarily high accuracy)
is usually obtained.
"Stability of Linear Algebra Computations
in Interior-Point Methods for Linear Programming")
Preprint MCS-P446-0694, June, 1994; revised July 1995.