Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

Kim-Chuan Toh (mattohkcmath.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