Product-form Cholesky factorization in interior point methods for second-order cone programming

• 成果类型: Article
• 署名作者: Goldfarb, D; Scheinberg, K
• 署名单位: Columbia University; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0556-1
• 发表日期: 2005
• 页码: 153-179
• 关键词: handling dense columns; algorithms

摘要

Second-order cone programming (SOCP) problems are typically solved by interior point methods. As in linear programming (LP), interior point methods can, in theory, solve SOCPs in polynomial time and can, in practice, exploit sparsity in the problem data. Specifically, when cones of large dimension are present, the density that results in the normal equations that are solved at each iteration can be remedied in a manner similar to the treatment of dense columns in an LP. Here we propose a product-form Cholesky factorization (PFCF) approach, and show that it is more numerically stable than the alternative Sherman-Morrison-Woodbury approach. We derive several PFCF variants and compare their theoretical performance. Finally, we prove that the elements of L in the Cholesky factorizations LDLT that arise in interior point methods for SOCP are uniformly bounded as the duality gap tends to zero as long as the iterates remain is some conic neighborhood of the cental path.