A Spectral Bundle Method with Bounds
C. Helmberg and K.C. Kiwiel
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.
Preprint SC 99-37,
Konrad-Zuse-Zentrum fuer Informationstechnik Berlin,
14195 Berlin, Germany,
December 1999
Contact: [email protected]
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)