4
$\begingroup$

According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."

What are the necessary conditions for strong duality to hold in semidefinite programming?

I would think this question would be easy to answer with a quick search, but instead I have ended up with many sources saying seemingly slightly different things. Let's go over them:

1. Lecture notes from CMU course. The relevant section is 12.3.1 The Strong Duality Theorem for SDPs.

Theorem 12.9. Assume both primal and dual have feasible solutions. Then $v_{\text{primal}} ≥ v_{\text{dual}}$, where $v_{\text{primal}}$ and $v_{\text{dual}}$ are the optimal values to the primal and dual respectively. Moreover, if the primal has a strictly feasible solution (a solution $x$ such that $x \succ 0$ or $x$ is positive definite) then 1) The dual optimum is attained (which is not always the case for SDPs) and 2) $v_{\text{primal}}$ = $v_{\text{dual}}$. Similarly, if the dual is strictly feasible, then the primal optimal value is achieved, and equals the dual optimal value. Hence, if both the primal and dual have strictly feasible solutions, then both $v_{\text{primal}}$ and $v_{\text{dual}}$ are attained.

The first part of this seems to imply that all you need is for the primal or the dual to have a strictly feasible solution. But then the very last line throws me off as it seems to imply that both need a strictly feasible solution.

2. Lecture notes from Berkeley course. The relevant section is 12.3.2 Strong Duality.

From Slater’s theorem, strong duality will hold if the primal problem is strictly feasible, that is, if there exist $X \succ 0$ such that $\langle A_i, X \rangle = b_i, i = 1, \ldots , m$. Using the same approach as above, one can show that the dual of problem (13.5) is precisely the primal problem (13.2). Hence, if the dual problem is strictly feasible, then strong duality also holds. Recall that we say that a problem is attained if its optimal set is not empty. It turns out that if both problems are strictly feasible, then both problems are attained.

I have the exact same problem with this one. It first seems to say you only need one of the two to be strictly feasible. Then it seems to imply that actually both must be strictly feasible. Or is it possible for strong duality to hold even when one of the two has an empty optimal set? I don't see how this makes sense.

3. Lecture notes from IIT Kanpur. The relevant section is 4 Extra reading: Strong duality, Slater’s condition.

Theorem 1. Given a semidefinite program in standard form with parameters $C, A_i , b$, suppose the feasible set of primal is $P$ and feasible set of dual is $D$. Then strong duality holds if either $D \ne \emptyset$ and there exists a strictly feasible $X ∈ P$, i.e., $X \succ 0$, $Ai • X = b_i \forall i$ or if $P \ne \emptyset$ and there exists a strictly feasible $y \in D$, i.e., $\sum_i y_i A_i - C \succ 0$.

This throws in an extra condition that neither of the previous two have. You need one of the two to be strictly feasible, and you need the other one to simply have some feasible solution.


I have also taken a look at Slater's condition which seems to imply that you just need either the primal or the dual to be strictly feasible.

Thanks in advance for helping me out! I only know the basics of SDP, so some level of detail would be appreciated. Also, any references to sources that better explain this stuff than the ones above would be appreciated.

$\endgroup$
9
  • 1
    $\begingroup$ You are only addressing linear semidefinite programming, which is convex. However, semidefinite programming may be nonlinear, in which case it is (generally?) non-convex. Slater's condition implies strong duality for convex primal problems. but this implication does not hold for non-convex problems, including nonlinear semidefinite programming problems. Read section 5.2.3 "Strong duality and Slater’s constraint qualification" of "Convex Optimization", Boyd and Vandenberghe, web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf $\endgroup$ Jul 18 '20 at 23:02
  • $\begingroup$ @MarkL.Stone All of the source I cited restrict themselves to linear semidefinite programming (they are introductory), yet still provide seemingly different formulations of SDP duality for linear semidefinite programs. I'm asking how to specifically apply Slater's condition to linear SDPs. In particular, do both the primal and dual need to have a strictly feasible solution? Or just one of them? The sources above are contradictory on this matter. If you want I could edit the title to say, "Conditions required for strong duality to hold for linear SDPs." $\endgroup$
    – kanso37
    Jul 18 '20 at 23:14
  • $\begingroup$ I think that for linear SDP, if Slater's condition holds for the primal, it also hold for the dual, thereby resoiving your confusion; $\endgroup$ Jul 18 '20 at 23:38
  • $\begingroup$ @MarkL.Stone So I take that to mean that you just need a strictly feasible (i.e., positive definite) solution for one of the two? It is strange then that these lecture notes are not clear on this and add all of this extra wording about "attainment," etc. $\endgroup$
    – kanso37
    Jul 18 '20 at 23:50
  • 2
    $\begingroup$ Keep in mind that one of the pair can be unbounded and the other infeasible. You'll need to decide whether strong duality should be considered satisfied in that case. $\endgroup$ Jul 19 '20 at 4:24
3
$\begingroup$

The following is from Section 2.2 of Semidefinite Programming for Combinatorial Optimization by Christoph Helmberg. Let's define \begin{align*} p^* &= \inf\{\langle C,X\rangle\,:\,X\text{ primal feasible}\},\\ d^* &= \sup\{\langle b,y\rangle\,:\,y\text{ dual feasible}\}. \end{align*} In particular, $p^*=\infty$ if the primal is infeasible, $d^*=-\infty$ if the dual is infeasible, $p^*=-\infty$ if the primal is unbounded and $q^*=\infty$ if the dual is unbounded. Then the situation can be summarized as follows (Corollary 2.2.6 in the reference cited above).

  1. If the primal is strictly feasible and $p^*$ is finite, then $p^*=d^*$ and there is a dual solution that achieves this value.
  2. If the dual is strictly feasible and $d^*$ is finite, then $p^*=d^*$ and there is a primal solution that achieves this value.
  3. If both the primal and the dual are strictly feasible, then $p^*=d^*$ and the value is attained for both problems.

So in order to guarantee $p^*=d^*$ it is sufficient that either one of the two problems is strictly feasible, but if we want a primal solution that achieves the value $p^*$ we should ask for a strictly feasible solution of the dual.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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