- | ||||
|
![]()
|
Solving large scale semidefinite programsvia an iterative solver onthe augmented systems
Kim-Chuan Toh (mattohkc 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 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 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: Large scale semidefinite programming, interior-point methods,augmented systems, conjugate residual method,symmetric quasi-minimal residual method, preconditioners,maximum-clique problem Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: Research Report B-388, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan, December 2002. Download: [Postscript] Entry Submitted: 01/20/2003 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |