Modified Cholesky Factorizations in Interior-Point Algorithms for
Linear Programming
Stephen Wright
We investigate a modified Cholesky algorithm typical of those used in
most interior-point codes for linear programming. Cholesky-based
interior-point codes are popular for three reasons: their
implementation requires only minimal changes to standard sparse
Cholesky algorithms (allowing us to take full advantage of software
written by specialists in that area); they tend to be more efficient
than competing approaches that use alternative factorizations; and
they perform robustly on most practical problems, yielding good
interior-point steps even when the coefficient matrix of the main
linear system to be solved for the step components is ill-conditioned.
We investigate this surprisingly robust performance by using
analytical tools from matrix perturbation theory and error analysis,
illustrating our results with computational experiments. Finally, we
point out the potential limitations of this approach.
Preprint ANL/MCS-P600-0596, Mathematics and Computer
Science Division, Argonne National Laboratory, May, 1996.
Revised June, 1998.
Contact: [email protected]
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)