Paper Info
Title
Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method
Abstract
Most current implementations of interior-point methods for semidefinite programming use a direct method to solve the Schur complement equation (SCE) $M \Delta y=h$ in computing the search direction. When the number of constraints is large, the problem of having insufficient memory to store M can be avoided if an iterative method is used instead. Numerical experiments have shown that the conjugate residual (CR) method typically takes a huge number of steps to generate a high accuracy solution. On the other hand, it is difficult to incorporate traditional preconditioners into the SCE, except for block diagonal preconditioners. We decompose the SCE into a 2 × 2 block system by decomposing $\Delta y$ (similarly for h) into two orthogonal components with one lying in a certain subspace that is determined from the structure of M. Numerical experiments on semidefinite programming problems arising from the Lovász $\theta$-function of graphs and MAXCUT problems show that high accuracy solutions can be obtained with a moderate number of CR steps using the proposed equation.
Year
DOI
Venue
2002
10.1137/S1052623400376378
SIAM Journal on Optimization
Keywords
Field
DocType
proposed equation,delta y,moderate number,conjugate residual method,interior-point method,huge number,large scale semidefinite programs,block diagonal preconditioners,block system,direct method,high accuracy solution,iterative method,interior point methods,schur complement,interior point method,iteration method
Discrete mathematics,Direct method,Residual,Mathematical optimization,Iterative method,Interior point method,Semidefinite programming,Block matrix,Mathematics,Schur complement,Conjugate residual method
Journal
Volume
Issue
ISSN
12
3
1052-6234
Citations 
PageRank 
References 
28
2.56
13
Authors
2
Name
Order
Citations
PageRank
Kim-Chuan Toh1109780.39
Masakazu Kojima21603222.51