Conditions required for strong duality to hold for SDPs

Question

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.

Answer 1

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.