# SDP具備強對偶性的條件

1。Lecture notes from CMU course。相關部分是12.3.1 SDP的強對偶定理。

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.

2。Lecture notes from Berkeley course。相關章節為12.3.2強對偶。

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.

3。Lecture notes from IIT Kanpur。相關章節為4額外閱讀：強對偶性，斯萊特的病情。

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

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.