Optimization Online


A Linear Programming Approach to Semidefinite Programming Problems

Kartik Krishnan (kartis***at***rpi.edu)
John Mitchell (mitchj***at***rpi.edu)

Abstract: 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 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 problems.

Keywords: semidefinite programming, linear programming, spectral bundle, eigenvalue optimisation, combinatorial optimisation, cutting plane approach

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Combinatorial Optimization

Citation: Department of Mathematical Sciences, 110 8th Street, Troy, NY, 12180 U.S.A. May 2001 http://www.rpi.edu/~mitchj/papers/cutsdpbundle.html

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 05/17/2001
Entry Accepted: 05/17/2001
Entry Last Modified: 07/23/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society