A Spectral Bundle Method for Semidefinite Programming

TLDR

Primal‑dual interior‑point methods for semidefinite programs cannot exploit problem structure, limiting them to small problems, while many combinatorial SDPs have sparse, large matrices. The authors aim to compute acceptable approximations to large SDPs quickly by replacing polyhedral cutting‑plane models with a semidefinite bundle model tailored to eigenvalue problems. They employ a semidefinite bundle method that substitutes polyhedral cuts with a semidefinite model for eigenvalue optimization, and they provide a convergence proof. Numerical experiments on combinatorial problems demonstrate that the approach is efficient.

Abstract

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 us 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 replacing the traditional polyhedral cutting plane model constructed from subgradient information by a semidefinite model that is tailored to eigenvalue problems. Convergence follows from the traditional approach but a proof is included for completeness. We present numerical examples demonstrating the efficiency of the approach on combinatorial examples.