<p>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 <a href="http://opus.kobv.de/zib/volltexte/2000/603/pdf/ZR-00-34.pdf">Habilitation thesis</a>, <a href="http://dx.doi.org/10.1016/S0927-0507%2805%2912008-8">this survey</a>, and <a href="http://www.math.cmu.edu/~reha/sdpco.html">this course page</a>  .</p>

<p>Another recent sequence of spectacular results making use of semidefinite programming is the application of Razborov's <a href="http://www.jstor.org/stable/10.2307/27588603">flag algebras</a> to prove results on Turan type problems (see <a href="http://people.cs.uchicago.edu/~razborov/files/flag_survey.pdf">this survey</a> and the <a href="http://flagmatic.org/">flagmatic project</a>).     </p>

CC BY-SA 3.0
2013-12-11T04:05:51.947Z
2013-12-11T04:05:51.947Z
Thomas Kalinowski
<p>A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. <a href="http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf">Goemans and Williamson</a> showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, <a href="http://www.cs.cornell.edu/~dsteurer/papers/lpsize.pdf">Chan, Lee, Raghavendra, and Steurer</a> showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve approximation no better than 0.5. </p>

<p>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 <a href="http://math.mit.edu/~rothvoss/lecturenotes/lasserresurvey.pdf">Rothvoß's survey</a> for a nice introduction. By now there are too many examples of successes of SDPs in optimization to list. Also, <a href="http://www.eecs.berkeley.edu/~prasad/Files/extabstract.pdf">Raghavendra showed</a> that one particular SDP gives the best approximation to all MaxCSP problems, if the Unique Games conjecture is true. </p>

<p>Check the books of <a href="http://link.springer.com/book/10.1007/978-3-642-22015-9">Gaertner and Matousek</a>, chapters 6 and 13 of <a href="http://link.springer.com/book/10.1007/978-3-642-22015-9">Willimson and Shmoys' book</a>, <a href="http://www.cs.elte.hu/~lovasz/semidef.ps">Lovasz's survey</a>. </p>

CC BY-SA 3.0
2013-12-11T05:04:30.070Z
2013-12-11T16:12:45.933Z
2013-12-11T16:12:45.933Z
Sasho Nikolov
<p>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. </p>

<p>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? </p>

<p>Thanks very much for any response.</p>

CC BY-SA 3.0
2013-12-11T12:40:45.867Z
Maybe you can make your question more precise? After all, linear programming is $\mathsf{P}$-complete.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-12-11T15:57:05.170Z
@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.
Sasho Nikolov
<linear-programming><convex-optimization><semidefinite-programming>
What can be solved with semidefinite programming that can't be solved with linear programming?
user11094
# What can be solved with semidefinite programming that can't be solved with linear programming?

(Asked by: username_0 on 2013-12-10)

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.

**Tags:** linear-programming, convex-optimization, semidefinite-programming

> **Comments:**
> **username_1**: Maybe you can make your question more precise? After all, linear programming is $\mathsf{P}$-complete.  
> **username_2**: @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.  

---

## 2 answers

### Answer by username_2 on 2013-12-11. Score: 18 | Accepted answer

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. [Goemans and Williamson](http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf) showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, [Chan, Lee, Raghavendra, and Steurer](http://www.cs.cornell.edu/~dsteurer/papers/lpsize.pdf) 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](http://math.mit.edu/~rothvoss/lecturenotes/lasserresurvey.pdf) for a nice introduction. By now there are too many examples of successes of SDPs in optimization to list. Also, [Raghavendra showed](http://www.eecs.berkeley.edu/~prasad/Files/extabstract.pdf) 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](http://link.springer.com/book/10.1007/978-3-642-22015-9), chapters 6 and 13 of [Willimson and Shmoys' book](http://link.springer.com/book/10.1007/978-3-642-22015-9), [Lovasz's survey](http://www.cs.elte.hu/~lovasz/semidef.ps).


---

### Answer by username_3 on 2013-12-11. Score: 12

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](http://opus.kobv.de/zib/volltexte/2000/603/pdf/ZR-00-34.pdf), [this survey](http://dx.doi.org/10.1016/S0927-0507%2805%2912008-8), and [this course page](http://www.math.cmu.edu/~reha/sdpco.html) .

Another recent sequence of spectacular results making use of semidefinite programming is the application of Razborov's [flag algebras](http://www.jstor.org/stable/10.2307/27588603) to prove results on Turan type problems (see [this survey](http://people.cs.uchicago.edu/~razborov/files/flag_survey.pdf) and the [flagmatic project](http://flagmatic.org/)).


---

