Numerically Stable Product-Form Cholesky (LDLT) Factorization Based Implementations of Interior Point Methods for Second-Order Cone Programming

Second-order cone programming (SOCP) problems are an extension of linear programming problems and are typically solved by applying interior point methods. Their practical complexity is close to that of the linear programming, except for when a cone of a very large dimension is present. In this case the normal equation which is solved at every iteration becomes very dense. This can be remedied in a similar manner to treating of the dense columns in the linear programming constraint matrix. Here we propose to apply the product form Cholesky factorization approach, which is more numerically stable than its alternative - the Sherman-Morrison-Woodbury approach. We derive a few variants of the PFCF, based on rank-one and rank-$k$ updates. We compare their theoretical perfomance. Finally, a key part of our theoretical analysis of the stability of the product form approach for SOCP is the proof that the elements of the Cholesky factors of the matrices that arise in IPMs for SOCP are uniformly bounded as the duality gap converges to zero under the assumption that the iterates remain is some conic neighborhood of the cental path.

By: D. Goldfarb, K. Scheinberg

Published in: Mathematical Programming , volume 103, (no 1), pages 153-79 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .