10
$\begingroup$

I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I already know that semidefinite programs are a generalization of linear programs.

Also, how does one recognize a problem that can be solved using semidefinite programming? What is a typical problem that semidefinite programming is used for that couldn't be solved via linear programming?

Thanks very much for any response.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Maybe you can make your question more precise? After all, linear programming is $\mathsf{P}$-complete. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Dec 11, 2013 at 12:40
  • 5
    $\begingroup$ @KristofferArnsfeltHansen I never stop wondering why people keep bringing this fact up in similar discussions. P-completeness is irrelevant unless we are talking about separating P from L or NC - if we are talking about polytime, everything in P is "P-complete". To suggest an answer to OP: once you fix a linear encoding of a problem, (i.e. write as optimizing a linear functional over a polytope) it makes perfect sense to ask whether a polysize LP/SDP can solve the problem. $\endgroup$
    – Sasho Nikolov
    Commented Dec 11, 2013 at 15:57

2 Answers 2

Reset to default
18
$\begingroup$

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve approximation no better than 0.5.

It's hard to say concisely what kind of problems usually benefit from an SDP. A systematic approach to constructing SDP relaxations is through hierarchies, the most powerful of which is the Lasserre hierarchy: see Rothvoß's survey for a nice introduction. By now there are too many examples of successes of SDPs in optimization to list. Also, Raghavendra showed that one particular SDP gives the best approximation to all MaxCSP problems, if the Unique Games conjecture is true.

Check the books of Gaertner and Matousek, chapters 6 and 13 of Willimson and Shmoys' book, Lovasz's survey.

Improve this answer
$\endgroup$
12
$\begingroup$

For many combinatorial optimization problems (for instance Max-Cut), semidefinite programming yields much stronger relaxations than the LP relaxation of IP formulations. This allows the design of approximation algorithms, and of exact algorithms which are more efficient than their linear counterparts due to the better quality of the bounds. Examples can be found in Christoph Helmberg's Habilitation thesis, this survey, and this course page .

Another recent sequence of spectacular results making use of semidefinite programming is the application of Razborov's flag algebras to prove results on Turan type problems (see this survey and the flagmatic project).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.