Optimization Online


Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

Kim-Chuan Toh (mattohkc***at***math.nus.edu.sg)

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
Entry Accepted: 01/20/2003
Entry Last Modified: 07/01/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society