Modified Cholesky Factorizations in Interior-Point Algorithms for Linear Programming
Stephen J. Wright · SIAM Journal on Optimization · 1999
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.
Cited by 54 works. doi:10.1137/s1052623496304712
Authors
References
- Solving Least Squares Problems
- Primal-Dual Interior-Point Methods
- Matrix perturbation theory
- Accuracy and Stability of Numerical Algorithms
- Accuracy and stability of numerical algorithms
- Matrix Perturbation Theory
- Computational experience with a primal-dual interior point method for linear programming
- Solving large-scale linear programs by interior-point methods under the Matlab ∗ Environment †
- The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm
- On the Automatic Scaling of Matrices for Gaussian Elimination