An interior-point method for semidefinite programming

Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, Henry Wolkowicz

Research output: Contribution to journalArticlepeer-review

459 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)342-361
Number of pages20
JournalSIAM Journal on Optimization
Volume6
Issue number2
DOIs
StatePublished - May 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Interior-point methods
  • Max-cut relaxations
  • Max-min eigenvalue problems
  • Semidefinite programming

Fingerprint Dive into the research topics of 'An interior-point method for semidefinite programming'. Together they form a unique fingerprint.

Cite this