A linear programming (LP) approach to semidefinite programming
(SDP) problems
Kartik Krishnan and John Mitchell
Until recently, the study of interior point methods has dominated
algorithmic research in semidefinite programming (SDP). From a
theoretical point of view, these interior point methods offer
everything one can hope for; they apply to all SDP's, exploit second
order information and offer polynomial time complexity. Still for
practical applications with many constraints $k$, the number of
arithmetic operations, per iteration is often too high. This motivates
the search for other approaches, that are suitable for large $k$ and
exploit problem structure. Recently Helmberg and Rendl developed a
scheme that casts SDP's with a constant trace on the primal feasible
set as eigenvalue optimization problems. These are convex nonsmooth
programming problems and can be solved by bundle methods. In this
paper we propose a linear programming framework to solving SDP's with
this structure. Although SDP's are {\em semi infinite} linear
programs, we show that only a small number of constraints, namely
those in the bundle maintained by the spectral bundle approach,
bounded by the square root of the number of constraints in the SDP,
and others polynomial in the problem size are typically required. The
resulting LP's can be solved rather quickly and provide reasonably
accurate solutions. We present numerical examples demonstrating the
efficiency of the approach on combinatorial examples.
Dept. of Mathematical Sciences, Rensselaer Polytechnic Institute,
110, 8th Street, Troy, NY, 12180. May 2001.
Contact: [email protected]