The cholesky factorization in interior point methods

AbstractThe paper concerns the Cholesky factorization of symmetric positive definite matrices arising in interior point methods. Our investigation is based on a property of the Cholesky factorization which interprets “small” diagonal values during factorization as degeneracy in the scaled optimization problem. A practical, scaling independent technique, based on the above property, is developed for the modified Cholesky factorization of interior point methods. This technique increases the robustness of Cholesky factorizations performed during interior point iterations when the optimization problem is degenerate. Our investigations show also the limitations of interior point methods with the recent implementation technology and floating point arithmetic standard. We present numerical results on degenerate linear programming problems of NETLIB