A Spectral Bundle Method for Semidefinite Programming
Christoph Helmberg and Franz Rendl
A central drawback of primal-dual 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.
ZIB Preprint SC 97-37, August 1997,
Konrad-Zuse-Zentrum fuer Informationstechnik Berlin,
Takustrasse 7,
D-14195 Berlin,
Germany.
Contact: [email protected]