An interior-point method for semidefinite programming

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

doi:10.1137/0806020

An interior-point method for semidefinite programming

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

Research output: Contribution to journal › Article › peer-review

534 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 language	English (US)
Pages (from-to)	342-361
Number of pages	20
Journal	SIAM Journal on Optimization
Volume	6
Issue number	2
DOIs	https://doi.org/10.1137/0806020
State	Published - May 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Applied Mathematics

Keywords

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

Access to Document

10.1137/0806020

Cite this

@article{c5c0da753d224dec9cbf2d2d71531ee4,

title = "An interior-point method for semidefinite programming",

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.",

keywords = "Interior-point methods, Max-cut relaxations, Max-min eigenvalue problems, Semidefinite programming",

author = "Christoph Helmberg and Franz Rendl and Vanderbei, {Robert J.} and Henry Wolkowicz",

year = "1996",

month = may,

doi = "10.1137/0806020",

language = "English (US)",

volume = "6",

pages = "342--361",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - An interior-point method for semidefinite programming

AU - Helmberg, Christoph

AU - Rendl, Franz

AU - Vanderbei, Robert J.

AU - Wolkowicz, Henry

PY - 1996/5

Y1 - 1996/5

N2 - 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.

AB - 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.

KW - Interior-point methods

KW - Max-cut relaxations

KW - Max-min eigenvalue problems

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=0030303838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030303838&partnerID=8YFLogxK

U2 - 10.1137/0806020

DO - 10.1137/0806020

M3 - Article

AN - SCOPUS:0030303838

SN - 1052-6234

VL - 6

SP - 342

EP - 361

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 2

ER -

An interior-point method for semidefinite programming

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this