Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A Spectral Bundle Method for Semidefinite Programming

Please always quote using this URN: urn:nbn:de:0297-zib-3067
  • A central drawback of interior point methods for semidefinite programs is their lack of ability to exploit problem structure in cost and coefficient matrices. This restricts applicability to problems of small dimension. Typically semidefinite relaxations arising in combinatorial applications have sparse and well structured cost and coefficient matrices of huge order. We present a method that allows to compute acceptable approximations to the optimal solution of large problems within reasonable time. Semidefinite programming problems with constant trace on the primal feasible set are equivalent to eigenvalue optimization problems. These are convex nonsmooth programming problems and can be solved by bundle methods. We propose to replace the traditional polyhedral cutting plane model constructed by means of subgradient information by a semidefinite model that is tailored for eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficacy of the approach on combinatorial examples.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Christoph Helmberg, Franz Rendl
Document Type:ZIB-Report
Date of first Publication:1997/08/19
Series (Serial Number):ZIB-Report (SC-97-37)
ZIB-Reportnumber:SC-97-37
Published in:Appeared in: SIAM J. Optim. 10 (2000) 673-696
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.