Iterative Approaches to Solving the Quadratic Semidefinite Subproblem of the Spectral Bundle Method

Christoph Helmberg^*

The spectral bundle method is tuned to solving semidefinite programs (SDP) with large semidefinite matrix variables having constant or bounded trace. For efficient bundle sizes, solving a quadratic semidefinite subproblem by interior point methods formed the bottleneck so far. We report on our experience (joint work in progress with K.C. Toh) with a preconditioned symmetric quasi minimal residual (PSQMR) approach for computing the Newton step in this interior point method like in the package QSDP. On our randomly generated test instances this results in significant savings. However, some semidefinite relaxations of combinatorial optimization problems indicate a strong connection to the quality of the selected scaling approach; this needs further work.

Mathematics Subject Classification: 90C22 90C06

Keywords: semidefinite optimization, large scale methods, eigenvalue optimization

Minisymposion: Algorithms Based on Semidefinite Optimization