A Spectral Bundle Method with Bounds (rev.Vers.SEP01)
Appeared in: Mathematical Programming 93 (2002) 173-194
| SC 99-37 | Christoph Helmberg, K.C. Kiwiel
A Spectral Bundle Method with Bounds (rev.Vers.SEP01) Appeared in: Mathematical Programming 93 (2002) 173-194 | |
Original Version
Abstract: Semidefinite relaxations of quadratic 0-1 programming or
graph
partitioning problems are well known to be of high
quality. However,
solving them by primal-dual interior point methods can
take much time
even for problems of moderate size. The recent spectral
bundle method
of Helmberg and Rendl can solve quite efficiently large
structured
equality-constrained semidefinite programs if the trace of
the primal
matrix variable is fixed, as happens in many applications.
We extend
the method so that it can handle inequality constraints
without
seriously increasing computation time.
Encouraging preliminary computational results are
reported.
Keywords: Eigenvalue optimization,
convex optimization
MSC: 90C25, 65F15, 52A41, 90C06