A Spectral Bundle Method with Bounds
Please always quote using this URN: urn:nbn:de:0297-zib-4256
- 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.
Author: | Christoph Helmberg, K.C. Kiwiel |
---|---|
Document Type: | ZIB-Report |
Tag: | Eigenvalue optimization; convex optimization |
MSC-Classification: | 52-XX CONVEX AND DISCRETE GEOMETRY / 52Axx General convexity / 52A41 Convex functions and convex programs [See also 26B25, 90C25] |
65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F15 Eigenvalues, eigenvectors | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C06 Large-scale problems | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C25 Convex programming | |
Date of first Publication: | 1999/10/29 |
Series (Serial Number): | ZIB-Report (SC-99-37) |
ZIB-Reportnumber: | SC-99-37 |
Published in: | Appeared in: Mathematical Programming 93 (2002) 173-194 |