本文轉自徐飛翔的“《SVM筆記系列之四》最優化問題的對偶問題”

版權聲明：本文為博主原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接和本聲明。

對偶問題

最優化問題存在對偶問題，所謂對偶問題，源于這個思想：

原始問題比較難以求解，通過構建其對偶問題，期望解決這個對偶問題得到其原問題的下界（在弱對偶情況下，對于最小化問題來說），或者得到原問題的解（強對偶情況下）。

在SVM中，因為其屬于凸優化問題，因此是強對偶問題，可以通過構建對偶問題解決得到原問題的解。我們舉一個線性規劃中一個經典問題，描述如下：

某工廠有兩種原料A、B，而且能用其生產兩種產品：

生產第一種產品需要2個A和4個B，能夠獲利6；生產第二種產品需要3個A和2個B，能夠獲利4；此時共有100個A和120個B，問該工廠最多獲利多少？可以簡單得到其問題的數學表達式為：

當然，得到這個式子的根據就是最大化其賣出去的產品的利潤。但是，如果只問收益的話，明顯地，還可以考慮賣出原材料A和B的手段，前提就是賣出原材料的盈利會比生產商品盈利高，假設產品A和產品B的單價為和，從這個角度看，只要最小化購買原材料的價格，我們就可以得出另一個數學表達式：

其實，我們可以發現這其實是極大極小問題和其對偶問題，極小極大問題。

一些定義原始問題我們要討論原問題和對偶問題，就需要一些定義，我們給出原始問題的非拉格朗日函數表達形式如式子( 1.1 ) 所示，引進其廣義拉格朗日函數：

其中，而和是拉格朗日乘子，其中由KKT條件有，考慮關于的函數：

這里下標P 用以表示這個是原始問題。聯想到我們在文章《SVM的拉格朗日函數表示以及其對偶問題》中一些關于對偶問題的討論，我們知道其實( 3.2 )中的其實就表示了( 1.1 ) 中的原問題的目標函數和其約束條件，這里再探討一下：假設我們存在一個x，使得x違反原始問題的約束條件，從而有或者，那么我們可以推論出：

為什么呢？ 因為若存在某個i使得， 那么就可以令使得取得無窮大這個“最大值”；同樣的，若存在一個j使得， 那么就總是可以使得讓， 而其他各個和均取為0（滿足約束條件的拉格朗日乘子取為0）。這樣，只有對于滿足約束條件的i和j，才會有成立。 于是我們有這個分段表達式：

所以，如果是最小化問題，我們有極小極大問題(3.5):

其與式子( 1.1 )是完全等價的，有著同樣的解。這樣一來，我們就把原始的最優化問題轉換為了廣義拉格朗日函數的極小極大問題，為了后續討論方便，我們記：

其中 為問題的解。

極小極大問題的對偶， 極大極小問題我們定義：

在考慮極大化( 3.7 )有：

式子( 3.8 ) 稱為廣義拉格朗日函數的極大極小問題，將其變成約束形式，為：

式子(3.9) 被稱為原問題的對偶問題，定義其最優解為：

實際上，通過這種方法我們可以將式子(2.1) 轉化為式子(2.2) ，也就是將原問題轉化為對偶問題，有興趣的朋友可以自行嘗試。

原始問題和對偶問題的關系正如前面所談到的，原始問題的解和對偶問題的解存在一定的關系，對于任意的，我們有：

等價于：

注意，式子(4.2) 對于所有的都成立，因為原始問題和對偶問題均有最優解，所以有：

容易得到：

由此我們得到了在最小化問題中的結論，這個稱為弱對偶。弱對偶指出，解決最小化問題的對偶問題可以得到原問題的解的下界。

既然有弱對偶就會存在強對偶。強對偶指的是的情況，在某些情況下，原始問題和對偶問題的解相同，這時可以用解決對偶問題來代替原始問題，下面以定理的方式給出強對偶成立的重要條件而不予以證明：

考慮原始問題(1.1) 和對偶問題(3.9)，假設和都是凸函數， 是仿射函數，并且不等式約束是嚴格可行的，既存在 X，對所有i有 ，則存在，使得 是原始問題的解， 是對偶問題的解（滿足這個條件的充分必要條件就是滿足KKT條件1），并且：

引用

1. 最優化問題學習筆記1-對偶理論 CSDN
2. 《統計學習方法》 豆瓣
3. 如何理解對偶問題？ feng liu的回答
4. 《拉格朗日乘數法和KKT條件的直觀解釋》 CSDN
5. SVM的拉格朗日函數表示以及其對偶問題 CSDN

1. 見《拉格朗日乘數法和KKT條件的直觀解釋》