On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

• 成果类型: Article
• 署名作者: Kocvara, Michal; Stingl, Michael
• 署名单位: Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Czech Technical University Prague; University of Erlangen Nuremberg
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0029-9
• 发表日期: 2007
• 页码: 413-444
• 关键词: interior-point methods; semidefinite programs; solving large; benchmarking; optimization; STABILITY

摘要

The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to avoid explicit calculation of the Newton matrix either by an implicit scheme in the matrix-vector product or using a finite-difference formula. This leads to huge savings in memory requirements and, for certain problems, to further speed-up of the algorithm.