Please use this identifier to cite or link to this item: https://doi.org/10.1137/S1052623402419819
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
Preconditioners
Symmetric quasi-minimal residual method
Issue Date: 2004
Source: 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. https://doi.org/10.1137/S1052623402419819
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
URI: http://scholarbank.nus.edu.sg/handle/10635/104147
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.

SCOPUSTM   
Citations

39
checked on Jan 10, 2018

WEB OF SCIENCETM
Citations

26
checked on Jan 10, 2018

Page view(s)

9
checked on Jan 15, 2018

Google ScholarTM

Check

Altmetric


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