AN INTERIOR-POINT METHOD FOR SEMIDEFINITE PROGRAMMING

We propose a new interior-point-based method to minimize a linear func tion of a matrix variable subject to linear equality and inequality co nstraints over the set of positive semidefinite matrices. We show that the approach is very efficient for graph bisection problems such as m ax-cut. Other applications include max-min eigenvalue problems and rel axations for the stable set problem.