<p>For the SDP in standard form
$$
\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},
$$
Slater's condition reduces to the existence of a positive definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the combinatorial optimization/approximation algorithms literature. For example, for the Goemans-Williamson Max-Cut SDP, the feasibility constraints are $\{X: X_{1,1} = 1, \ldots, X_{n,n} = 1, X\succeq 0\}$ and the identity matrix is a positive definite feasible solution.</p>

<p>As far as the Lasserre/Sum of Squares hierarchy, <a href="http://epubs.siam.org/doi/abs/10.1137/S1052623400366802" rel="nofollow">Lasserre showed</a> that if the feasible set determined by the polynomial constraints has an interior point, then there is no duality gap. You can find a weaker condition in <a href="http://arxiv.org/abs/1405.7334" rel="nofollow">this paper</a>.</p>

CC BY-SA 3.0
2016-08-15T14:54:49.223Z
Thanks a lot for the references! So is the transformed Slater's condition also a necessary condition for the SDP? Or are there other necessary conditions? (I am soon going to look through the papers that you referred to but I was wondering if you could say something about what you meant by "weaker condition"? You mean the condition in the second paper is still a sufficient condition and not a necessary condition but is simpler than the sufficient condition in the first paper?)
gradstudent
CC BY-SA 3.0
2016-08-15T21:33:35.917Z
This is the standard Slater condition, I have just specialized to SDPs, which simplifies matters because all constraints are affine, except for the PSD constraint. This condition is not necessary. I do not think either of the SoS conditions is necessary either, but the "weaker" one does not require the existence of an interior point, so it may be easier to verify.
Sasho Nikolov
CC BY-SA 3.0
2016-08-15T22:18:49.733Z
Thanks! So a necessary condition is not known?
gradstudent
CC BY-SA 3.0
2016-08-13T14:20:19.187Z
2016-08-15T02:31:05.953Z
2016-08-15T02:31:05.953Z
Sasho Nikolov
<p>There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions.</p>

<p>We say that the semidefinite {\em system} </p>

<p><span class="math-container">$(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$</span></p>

<p>is <strong>badly behaved</strong> if here is an objective function <span class="math-container">$c$</span> for which the SDP</p>

<p><span class="math-container">$\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$</span></p>

<p>has a finite optimal value, but the dual SDP does not have  a solution with the same value: i.e., strong duality fails for some <span class="math-container">$c.$</span> </p>

<p><span class="math-container">$(P_{SD})$</span>  is <strong>well behaved</strong> if it is not badly  behaved. That is, for every objective function strong duality holds. (I.e., for every <span class="math-container">$c$</span> for which the primal SDP has a finite optimal value, the dual has a solution with the same value). </p>

<p>Of course,  if Slater's condition holds, then <span class="math-container">$(P_{SD})$</span> is well behaved, but the converse is not true.</p>

<p><a href="https://arxiv.org/pdf/1709.02423.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1709.02423.pdf</a></p>

<p>The  paper is coming out soon in SIAM Review. I hope people will like it :)</p>

CC BY-SA 4.0
2019-09-17T20:43:22.650Z
2019-09-19T21:34:52.983Z
2019-09-19T21:34:52.983Z
district9
<p>There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition.  This is due to <a href="https://scholar.google.com/scholar?cluster=17605171318595109451&amp;hl=en&amp;as_sdt=400005&amp;sciodt=0,14">Ramana</a>.  (For another take on this involving SOS, see <a href="http://arxiv.org/abs/1207.1691">[KS12]</a>.)  To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.</p>

<p>One notable consequence of this work is that the problem of testing whether a given SDP is feasible is in NP if and only if it is in coNP.  (However, I think the experts expect the problem is in neither.  The best upper bound known is PSPACE.)</p>

CC BY-SA 3.0
2016-08-18T15:58:44.020Z
Thanks a lot for very helpful reply! Let me look this up! (What a coincidence that over the last weeks I have also been trying to work through your paper with Daniel Kane on deep net circuit lower bounds! It is such an educative paper! I have been wondering if what you do for LTF also happens for more realistic activations like ReLU.)
gradstudent
CC BY-SA 3.0
2016-08-18T11:58:48.300Z
2016-08-18T11:58:48.300Z
Ryan O'Donnell
<p>I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?</p>

<p>For example, when one goes back and forth between the Lasserre and the SOS SDP, in principle one has a duality gap. However, somehow there seems to be some "trivial" reason why this gap isn't there. </p>

<p><a href="https://en.wikipedia.org/wiki/Slater%27s_condition" rel="nofollow noreferrer">Slater's condition</a> seems to be sufficient but not necessary and it applies to all convex programs. I am hoping that for SDPs in particular something stronger might be true. I would be equally happy to see any explicit example of using <a href="https://en.wikipedia.org/wiki/Slater%27s_condition" rel="nofollow noreferrer">Slater's condition</a> to prove the vanishing of the duality gap. </p>

<approximation-hardness><convex-optimization><semidefinite-programming><sum-of-squares><primal-dual>
When is the duality gap of semidefinite programming (SDP) zero?
gradstudent
# When is the duality gap of semidefinite programming (SDP) zero?

(Asked by: username_0 on 2016-08-13)

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?

For example, when one goes back and forth between the Lasserre and the SOS SDP, in principle one has a duality gap. However, somehow there seems to be some "trivial" reason why this gap isn't there.

[Slater's condition](https://en.wikipedia.org/wiki/Slater%27s_condition) seems to be sufficient but not necessary and it applies to all convex programs. I am hoping that for SDPs in particular something stronger might be true. I would be equally happy to see any explicit example of using [Slater's condition](https://en.wikipedia.org/wiki/Slater%27s_condition) to prove the vanishing of the duality gap.

**Tags:** approximation-hardness, convex-optimization, semidefinite-programming, sum-of-squares, primal-dual


---

## 3 answers

### Answer by username_3 on 2016-08-18. Score: 10 | Accepted answer

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to [Ramana](https://scholar.google.com/scholar?cluster=17605171318595109451&hl=en&as_sdt=400005&sciodt=0,14). (For another take on this involving SOS, see [[KS12]](http://arxiv.org/abs/1207.1691).) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.

One notable consequence of this work is that the problem of testing whether a given SDP is feasible is in NP if and only if it is in coNP. (However, I think the experts expect the problem is in neither. The best upper bound known is PSPACE.)

> **Comments:**
> **username_0**: Thanks a lot for very helpful reply! Let me look this up! (What a coincidence that over the last weeks I have also been trying to work through your paper with Daniel Kane on deep net circuit lower bounds! It is such an educative paper! I have been wondering if what you do for LTF also happens for more realistic activations like ReLU.)  

---

### Answer by username_1 on 2016-08-13. Score: 9

For the SDP in standard form
$$
\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A\_1^T X) = b\_1, \ldots, \mathrm{tr}(A\_m^T X) = b\_m, X \succeq 0\},
$$
Slater's condition reduces to the existence of a positive definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A\_i^T X) = b\_i$. I would guess this is satisfied for any SDP you can find in the combinatorial optimization/approximation algorithms literature. For example, for the Goemans-Williamson Max-Cut SDP, the feasibility constraints are $\{X: X\_{1,1} = 1, \ldots, X\_{n,n} = 1, X\succeq 0\}$ and the identity matrix is a positive definite feasible solution.

As far as the Lasserre/Sum of Squares hierarchy, [Lasserre showed](http://epubs.siam.org/doi/abs/10.1137/S1052623400366802) that if the feasible set determined by the polynomial constraints has an interior point, then there is no duality gap. You can find a weaker condition in [this paper](http://arxiv.org/abs/1405.7334).

> **Comments:**
> **username_0**: Thanks a lot for the references! So is the transformed Slater's condition also a necessary condition for the SDP? Or are there other necessary conditions? (I am soon going to look through the papers that you referred to but I was wondering if you could say something about what you meant by "weaker condition"? You mean the condition in the second paper is still a sufficient condition and not a necessary condition but is simpler than the sufficient condition in the first paper?)  
> **username_1**: This is the standard Slater condition, I have just specialized to SDPs, which simplifies matters because all constraints are affine, except for the PSD constraint. This condition is not necessary. I do not think either of the SoS conditions is necessary either, but the "weaker" one does not require the existence of an interior point, so it may be easier to verify.  
> **username_0**: Thanks! So a necessary condition is not known?  

---

### Answer by username_2 on 2019-09-17. Score: 1

There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions.

We say that the semidefinite {\em system}

$(P\_{SD}) \,\, \sum\_{i=1}^m x\_i A\_i \preceq B$

is **badly behaved** if here is an objective function $c$ for which the SDP

$\sup c^T x \,\, s.t. \,\, \sum\_{i=1}^m x\_i A\_i \preceq B$

has a finite optimal value, but the dual SDP does not have a solution with the same value: i.e., strong duality fails for some $c.$

$(P\_{SD})$ is **well behaved** if it is not badly behaved. That is, for every objective function strong duality holds. (I.e., for every $c$ for which the primal SDP has a finite optimal value, the dual has a solution with the same value).

Of course, if Slater's condition holds, then $(P\_{SD})$ is well behaved, but the converse is not true.

<https://arxiv.org/pdf/1709.02423.pdf>

The paper is coming out soon in SIAM Review. I hope people will like it :)


---

