An Interior-Point Method for Semidefinite Programming

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