《《2016 An Interior-Point Method for Semidefinite Programming》.pdf

An Interior-Point Method for Semidefinite Programming Christoph Helmberg ∗ Franz Rendl † Robert J. Vanderbei ‡ Henry Wolkowicz § January 18, 2005 Program in Statistics Operations Research Princeton University Princeton, NJ 08544 January 18, 2005 Revised October 1994 Abstract 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 show that the approach is very efficient for graph bisection problems, such as max-cut. Other applications include max-min eigenvalue problems and relaxations for the stable set problem. Key words: semidefinite programming, interior-point methods, max-cut relaxations, max-min eigenvalue problems. AMS 1991 Subject Classification: Primary 65F15, Secondary 49M35, 90C48 ∗Technische Universit¨at Graz, Institut f¨ur Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f¨ur Diskrete Optimierung. †Technische Universit¨at Graz, Institut f¨ur Mathematik, Kopernikusgasse 24, A-8010 Graz, Austria. Research support by Christian Doppler Laboratorium f¨ur Diskrete Optimierung. ‡Research support by AFOSR through grant AFOSR-91-0359. §Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont., Canada. This author thanks the Department of Civil Engineering and Operations Research, Princeton Univer-