Solving some large scale semidefinite programs via the conjugate residual method

Kim-Chuan Toh and Masakazu Kojima

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\times 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 Lov\'{a}sz $\theta$-function of graphs and MAXCUT problems show that high accuracy solutions can be obtained with moderate number of CR steps using the proposed equation.

Research Report, Department of Mathematics, National University of Singapore, August 2000