10
$\begingroup$

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 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 to prove the vanishing of the duality gap.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

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. (For another take on this involving SOS, see [KS12].) 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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – gradstudent
    Aug 18, 2016 at 15:58
9
$\begingroup$

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 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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?) $\endgroup$
    – gradstudent
    Aug 15, 2016 at 14:54
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Aug 15, 2016 at 21:33
  • $\begingroup$ Thanks! So a necessary condition is not known? $\endgroup$
    – gradstudent
    Aug 15, 2016 at 22:18
1
$\begingroup$

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 :)

Improve this answer
$\endgroup$

Your Answer

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