A Boundary Point Method to Solve Semidefinite Programs

✍ Scribed by J. Povh; F. Rendl; A. Wiegele

• Publisher: Springer Vienna
• Year: 2006
• Tongue: English
• Weight: 107 KB
• Volume: 78
• Category: Article
• ISSN: 0010-485X
• DOI: 10.1007/s00607-006-0182-2

✦ Synopsis

We investigate the augmented Lagrangian penalty function approach to solve semidefinite programs. It turns out that this method generates iterates which lie on the boundary of the cone of semidefinite matrices which are driven to the affine subspace described by the linear equations defining the semidefinite program. We provide some computational experience with this method and show in particular, that it allows to compute the theta number of a graph to reasonably high accuracy for instances which are beyond reach by other methods.