Stability of augmented system factorizations in interior-point methods. (English) Zbl 0878.65041

An analysis of ill-conditioned linear systems with large, sparse and symmetric matrix that arise in primal-dual interior-point methods for linear programming is carried out. The linear systems based on augmented system formulation are examined and it is observed how various standard factorization algorithms (the Bunch-Parlett, Bunch-Kaufman, and sparse Bunch-Parlett algorithms) for the system behave as its ill-conditioning grows without bound.
Numerical experiments indicate that for degenerate linear programming problems the computed search direction is so inaccurate that the interior-point method can move only a tiny distance along it but if the underlying linear program has a unique primal-dual solution then steps produced by standard factorization are often accurate enough to converge to high accuracy. The effects of roundoff errors are tracked by using standard techniques from backward error analysis.


65K05 Numerical mathematical programming methods
90C05 Linear programming
65F05 Direct numerical methods for linear systems and matrix inversion


Full Text: DOI