Please use this identifier to cite or link to this item:
Title: Solving large scale semidefinite programs via an iterative solver on the augmented systems
Authors: Toh, K.-C. 
Keywords: Augmented systems
Conjugate residual method
Interior-point methods
Large scale semidefinite programming
Maximum-clique problem
Symmetric quasi-minimal residual method
Issue Date: 2004
Citation: Toh, K.-C. (2004). Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM Journal on Optimization 14 (3) : 670-698. ScholarBank@NUS Repository.
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.
Source Title: SIAM Journal on Optimization
ISSN: 10526234
DOI: 10.1137/S1052623402419819
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 14, 2018


checked on Nov 28, 2018

Page view(s)

checked on Jul 27, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.