Solving large scale semidefinite programs via an iterative solver on the augmented systems
Citations
Altmetric:
Alternative Title
Abstract
The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that a diagonally preconditioned conjugate residual method on the SCE typically takes a huge number of steps to converge. However, it is difficult to incorporate cheap and effective preconditioners into the SCE. This paper proposes to apply the preconditioned symmetric quasi-minimal residual (PSQMR) method to a reduced augmented equation that is derived from the augmented equation by utilizing the eigenvalue structure of the interior-point iterates. Numerical experiments on SDP problems arising from maximum clique and selected SDPLIB (SDP Library) problems show that moderately accurate solutions can be obtained with a modest number of PSQMR steps using the proposed preconditioned reduced augmented equation. An SDP problem with 127600 constraints is solved in about 6.5 hours to an accuracy of 10 -6 in relative duality gap.
Keywords
Augmented systems, Conjugate residual method, Interior-point methods, Large scale semidefinite programming, Maximum-clique problem, Preconditioners, Symmetric quasi-minimal residual method
Source Title
SIAM Journal on Optimization
Publisher
Series/Report No.
Collections
Rights
Date
2004
DOI
10.1137/S1052623402419819
Type
Article