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Δ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 Δ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 θ-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.