## 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

Contact: mattohkc@math.nus.edu.sg