SDP具備強對偶性的條件


4

根據Wikipedia,當"原始最優目標和對偶最優目標相等"時,強對偶性成立。

在半定編程中保持強對偶性的必要條件是什麼?

我認為通過快速搜索可以輕鬆回答這個問題,但最終我得到了很多消息,說的話似乎有些不同。讓我們越過它們:

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

這帶來了前兩個都不具備的額外條件。您需要兩者中的一個嚴格可行,而您另一個需要簡單地擁有一些可行的解決方案。


我也查看了Slater's condition,這似乎意味著您只需要原始對偶就可以嚴格可行。

預先感謝您的幫助!我只知道SDP的基礎知識,所以一定程度的細節將不勝感激。另外,凡是引用比上述內容更能解釋這些內容的資源,都將受到讚賞。

3

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.