Solving Sparse Semidefinite Programs Using the Dual Scaling Algorithm with an Iterative Solver

C. Choi and Y. Ye

Recently, the dual-scaling interior-point algorithm has been used to solve large-scale semidefinite programs arisen from discrete optimization, since it better exploits the sparsity structure of the problems than several other interior-point methods, while retain the same polynomial time complexity. However, solving a linear system of a fully dense Gram matrix in each iteration of the algorithm becomes the time-bottleneck of computational efficiency. To overcome this difficulty, we have tested using an iterative method, the conjugate gradient method with a simple preconditioner, to solve the linear system for a prescribed accuracy. In this report, we report computational results of solving semidefinite programs with dimension up to 14,000, which show that the iterative method could save computation time up-to 25 times of using the directed Cholesky factorization solver.

Working Paper, Department of Management Sciences The University of Iowa Iowa City, Iowa 52242, U.S.A., March 2000