Monday, December 6, 2010

SDP

Linear programming was in fashion long before approximation algorithms. Linear programming exactly solves all sorts of important problems such as shortest paths, max flow, min cut, various kinds of preemptive scheduling, etc. What about semidefinite-definite programming? What is it good for, other than for approximation algorithms? What problems can be solved exactly by semi-definite programming?

9 comments:

  1. Sounds like an excellent question for cstheory.stackexchange.com :)

    ReplyDelete
  2. It's used in practice to help solve Max-Cut instances optimally, with applications to statistical physics. At least, that's what this paper seems to say:

    http://www.springerlink.com/content/w517512266886301/

    ReplyDelete
  3. Determining the optimal distortion for embedding a finite metric space into L_2.

    ReplyDelete
  4. In the area of polynomial optimization, the question of minimizing or maximizing the value of a polynomial reduces to asking if a given polynomial is non-negative by modifying the constant term. One way to guarantee that a polynomial is non-negative is to describe it as a sum of squares of smaller-degree polynomials. This sum-of-squares problem is solved by SDP.

    See http://www-user.tu-chemnitz.de/~helmberg/sdp_poly.html for a list of papers on the subject. See Week 1 of the MSRI summer graduate workshop on Algebraic, Geometric, and Combinatorial Methods for Optimization for a tutorial: http://www.msri.org/web/msri/scientific/workshops/summer-graduate-workshops/show/-/event/Wm533

    ReplyDelete
  5. Stephen Boyd's book has many examples. SDP, as well as convex programs more generally, are used to solve many continuous optimization problems that arise in engineering.

    ReplyDelete
  6. Does Max Cut in planar graphs count? It can be solved by a very large LP with a separation oracle, but also by a polynomial size SDP.

    ReplyDelete
  7. I'm not sure the max-cut and L2 distortion answers "nail" this... the examples Claire gave of important problems solved by LP have an importance outside the world of TCS research (indeed, LP experts have long tended to be OR/industrial engineers). Can we say the same for, e.g., max-cut? When is it important to find the optimal max cut in a graph?

    I ask out of genuine curiosity, not to be snarky. Personally, I love the beautiful theory surrounding max-cut.

    ReplyDelete
  8. SDPs are used every so often in machine learning. One application I believe is in learning kernels, see for example:
    http://cosmal.ucsd.edu/~gert/papers/lanckriet03a.pdf

    ReplyDelete
  9. Perhaps elaborating on Shaddin's comment above, Lovasz in Section 4.4 of this survey shows how solving an SDP can be used to give a sufficient condition for asymptotic stability of solutions of linear systems that satisfy a certain class of differential equations.

    ReplyDelete

Note: Only a member of this blog may post a comment.