學習筆記，僅供參考，有錯必糾
轉載自：李競宜

---

拉格朗日對偶問題

關于對拉格朗日對偶的理解，Boyd的那本《Convex Optimization》中給出了很多種解釋方法，比如通過函數值集合理解、鞍點解釋、博弈解釋和經濟學解釋等，我認為除了基于價格和稅的經濟學解釋比較符合題目要求的通俗解釋之外，其他的理解方法直接閱讀，對于初學者來說都算不上通俗，比較生澀難懂，尤其是對線性代數不夠熟練的情況下。

這里仍然采用Boyd那本書中5.3.1節通過函數值集合理解強弱對偶性，原書中先進行了具有一般性的理論推導，然后才進行了一個舉例幫助理解，沒有看懂前面的推導可能并不知道后面的簡化情形在講什么東西。這里采用相反的思路并且更加詳細的說明這個問題，首先使用一個簡單的例子直觀地理解強弱對偶性，然后再推廣到更一般的情況。這樣有利于更加通俗地理解這個問題。

首先，我們考慮只有一個不等式約束的優化問題$P_1$：

公式(2)是很容易理解的，在有定義的點集內取一個最小的$t$對應于原問題最優值的描述。現在假設$G$在$t$與$\mu$的二維空間圖像如下圖所示，并在圖中作出了$p^{?}$對應的位置。 不要忘記這里需滿足$\mu \le 0$，所以$p^{?}$是左邊第二象限“凸出”的部分對應的$t$而不在右邊.

接著，根據(2)的形式給出Lagrange對偶函數：

理解：這里的先取最小再取最大，是指對于所有$\lambda$的$f(\lambda )$先計算定義域$G$內的最小值，得到最小值集合. 再取集合中的最大值，該最大值對應得$\lambda$就是我們需要的值.

將直線$\lambda \mu +t?b=0$繪制在之前得到$t$與$\mu$的平面中，如下圖所示：

可以容易地得出斜率比較大和斜率比較小時， 可行域內最小$g(\lambda )$就是與 $G$的兩個“凸出”邊緣相切的時候，到這里有一種情況已經呼之欲出了，沒錯，就是直線剛好與$G$“凸出”的兩個邊緣同時相切的時候。現在講三種情況都繪制在同一張圖上，如下圖：

到這里，我們要從一簇 $g(\lambda )$中找出一個最大的這個任務也完成了，很顯然就是圖中的$d^{?}$ 。可以從圖中看出，在這個 $G$下是弱對偶性，原諒色那段代表的即是最優對偶間隙 $p^{?}?d^{?}$ 。

我們上面給出的$G$顯然是一個非凸集，現在將$G$更換為一個凸集，再來看看會發生什么：

很顯然，在$G$是是凸集的情況下，最優對偶間隙為0，成為強對偶。那么又有一個問題隨著而來了，只有$G$ 是凸集才滿足強對偶嗎？即 $G$為凸集是否是強對偶的充分必要條件？

答案當然是否定的，我們隨便可以給出一個反例，比如下圖這個丑丑的爪子狀的東西是個非凸集，但是最優對偶間隙還是0，因此我們可以得出結論， 是凸集是強對偶的充分非必要條件。實際上，這就是有名的Slater條件了。
至于強對偶的充分必要條件究竟是什么，這就涉及到另外一個更加有名的KKT條件了，KKT條件已經有些答主寫的非常詳細了，盡管我認為還是不夠通俗，但是認真讀下去還是可以解決大部分問題，關于KKT條件這里就不展開了。

至此，我們探討了在僅有一個不等式約束情況下強弱對偶性的幾何理解，接著我們應該要講問題拓展到一般情形下。后面的內容我基本上直接采用Boyd的《Convex Optimization》中的描述，如果目的只是想簡要、感性地理解強弱對偶性，下面的內容可以不用看了。另一方面，如果再看下面內容的時候覺得有些關于法向量和超平面相關的內容無法理解的話，說明對線性代數的知識還是不夠完備，可以考慮出門右拐加強一下線性代數，個人比較推薦MIT的公開課。

將$P_1$拓展為更加具有一般性的$P_2$，即：

接著，得到原問題的Lagrange對偶函數：

其中 $(\lambda ,\nu ,1{)}^T(\mu ,v,t)$是原問題的Lagrange函數，特別地，如果下確界有限，則不等式(6)定義了一個集合 $G$ 的支撐超平面。這個支撐超平面有時稱為非豎直超平面，這是因為法向量的最后一個分量不為零。在高維空間中支撐超平面對應于前面部分我們通過作圖觀察得到的直線方程:

$$(\lambda ,\nu ,1{)}^T(\mu ,v,t)\ge g(\lambda ,\nu )\text{\hspace{1em}(6)}$$

總結

以上是生活随笔為你收集整理的如何通俗理解拉格朗日对偶问题(part2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。