An interior point method for semidefinite programming

C. Helmberg and F. Rendl and R. J. Vanderbei and H. Wolkowicz

We propose a new interior point based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We present a theoretical convergence analysis, and show that the approach is very efficient for graph bisection problems, such as max-cut. The approach can also be applied to max-min eigenvalue problems.

Research Report, University of Waterloo. To appear in SIOPT.