A Spectral Bundle Method for Semidefinite Programming

摘要: A central drawback of primal-dual interior point methods for semidefinite programs is their lack ability to exploit problem structure in cost and coefficient matrices. This restricts applicability problems small dimension. Typically, relaxations arising combinatorial applications have sparse well-structured matrices huge order. We present a method that allows us compute acceptable approximations the optimal solution large within reasonable time. Semidefinite programming with constant trace on primal feasible set are equivalent eigenvalue optimization problems. These convex nonsmooth can be solved by bundle methods. propose replacing traditional polyhedral cutting plane model constructed from subgradient information tailored Convergence follows approach but proof included completeness. numerical examples demonstrating efficiency examples.