On a property of the Cholesky factorization and its consequences in interior point methods

Cs. Meszaros

The paper concerns the Cholesky factorization of symmetric positive definite matrices resulting from some matrix $F$ by computing $FF^{T}$. Our investigation is based on a theorem which shows that ''small'' diagonal values in the Cholesky factorization indicate rows of $F$ which lies close to the subspace spanned by the preceding rows. A practical, scaling independent technique, based on the above property, is developed for the modified Cholesky factorization. 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 the degenerate linear programming problems of NETLIB.

WP 98-7 Laboratory of Operations Research and Decision Systems Hungarian Academy of Sciences

Contact: meszaros@sztaki.hu