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?
Subscribe to:
Post Comments (Atom)
Sounds like an excellent question for cstheory.stackexchange.com :)
ReplyDeleteIt'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:
ReplyDeletehttp://www.springerlink.com/content/w517512266886301/
Determining the optimal distortion for embedding a finite metric space into L_2.
ReplyDeleteIn 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.
ReplyDeleteSee 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
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.
ReplyDeleteDoes 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.
ReplyDeleteI'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?
ReplyDeleteI ask out of genuine curiosity, not to be snarky. Personally, I love the beautiful theory surrounding max-cut.
SDPs are used every so often in machine learning. One application I believe is in learning kernels, see for example:
ReplyDeletehttp://cosmal.ucsd.edu/~gert/papers/lanckriet03a.pdf
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