A subspace semidefinite programming for spectral graph partitioning

A semidefinite program (SDP) is an optimization problem over n x n symmetric matrices where a linear function of the entries is to be minimized subject to linear equality constraints, and the condition that the unknown matrix is positive semidefinite. Standard techniques for solving SDP's require O(n(3)) operations per iteration. We introduce subspace algorithms that greatly reduce the cost os solving large-scale SDP's. We apply these algorithms to SDP approximations of graph partitioning problems. We numerically compare our new algorithm with a standard semidefinite programming algorithm and show that our subspace algorithm performs better.