本文轉(zhuǎn)自徐飛翔的“《SVM筆記系列之四》最優(yōu)化問題的對偶問題”
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
對偶問題
最優(yōu)化問題存在對偶問題，所謂對偶問題，源于這個思想：
原始問題比較難以求解，通過構(gòu)建其對偶問題，期望解決這個對偶問題得到其原問題的下界（在弱對偶情況下，對于最小化問題來說），或者得到原問題的解（強對偶情況下）。
在SVM中，因為其屬于凸優(yōu)化問題，因此是強對偶問題，可以通過構(gòu)建對偶問題解決得到原問題的解。我們舉一個線性規(guī)劃中一個經(jīng)典問題，描述如下：
某工廠有兩種原料A、B，而且能用其生產(chǎn)兩種產(chǎn)品：
生產(chǎn)第一種產(chǎn)品需要2個A和4個B，能夠獲利6；生產(chǎn)第二種產(chǎn)品需要3個A和2個B，能夠獲利4；此時共有100個A和120個B，問該工廠最多獲利多少？可以簡單得到其問題的數(shù)學表達式為：
當然，得到這個式子的根據(jù)就是最大化其賣出去的產(chǎn)品的利潤。但是，如果只問收益的話，明顯地，還可以考慮賣出原材料A和B的手段，前提就是賣出原材料的盈利會比生產(chǎn)商品盈利高，假設產(chǎn)品A和產(chǎn)品B的單價為和
，從這個角度看，只要最小化購買原材料的價格，我們就可以得出另一個數(shù)學表達式：
其實，我們可以發(fā)現(xiàn)這其實是極大極小問題和其對偶問題，極小極大問題。
一些定義原始問題我們要討論原問題和對偶問題，就需要一些定義，我們給出原始問題的非拉格朗日函數(shù)表達形式如式子( 1.1 ) 所示，引進其廣義拉格朗日函數(shù)：
其中，而
和
是拉格朗日乘子，其中由KKT條件有
，考慮關(guān)于
的函數(shù)：
這里下標P 用以表示這個是原始問題。聯(lián)想到我們在文章《SVM的拉格朗日函數(shù)表示以及其對偶問題》中一些關(guān)于對偶問題的討論，我們知道其實( 3.2 )中的其實就表示了( 1.1 ) 中的原問題的目標函數(shù)和其約束條件，這里再探討一下：假設我們存在一個x，使得x違反原始問題的約束條件，從而有
或者
，那么我們可以推論出：
為什么呢？ 因為若存在某個i使得， 那么就可以令
使得
取得無窮大這個“最大值”；同樣的，若存在一個j使得
， 那么就總是可以使得
讓
， 而其他各個
和
均取為0（滿足約束條件的拉格朗日乘子取為0）。這樣，只有對于滿足約束條件的i和j，才會有
成立。 于是我們有這個分段表達式：
所以，如果是最小化問題，我們有極小極大問題(3.5):
其與式子( 1.1 )是完全等價的，有著同樣的解。這樣一來，我們就把原始的最優(yōu)化問題轉(zhuǎn)換為了廣義拉格朗日函數(shù)的極小極大問題，為了后續(xù)討論方便，我們記：
其中 為問題的解。
極小極大問題的對偶， 極大極小問題我們定義：
在考慮極大化( 3.7 )有：
式子( 3.8 ) 稱為廣義拉格朗日函數(shù)的極大極小問題，將其變成約束形式，為：
式子(3.9) 被稱為原問題的對偶問題，定義其最優(yōu)解為：
實際上，通過這種方法我們可以將式子(2.1) 轉(zhuǎn)化為式子(2.2) ，也就是將原問題轉(zhuǎn)化為對偶問題，有興趣的朋友可以自行嘗試。
原始問題和對偶問題的關(guān)系正如前面所談到的，原始問題的解和對偶問題的解存在一定的關(guān)系，對于任意的，我們有：
等價于：
注意，式子(4.2) 對于所有的都成立，因為原始問題和對偶問題均有最優(yōu)解，所以有：
容易得到：
由此我們得到了在最小化問題中的結(jié)論，這個稱為弱對偶。弱對偶指出，解決最小化問題的對偶問題可以得到原問題的解的下界。
既然有弱對偶就會存在強對偶。強對偶指的是的情況，在某些情況下，原始問題和對偶問題的解相同，這時可以用解決對偶問題來代替原始問題，下面以定理的方式給出強對偶成立的重要條件而不予以證明：
考慮原始問題(1.1) 和對偶問題(3.9)，假設
和
都是凸函數(shù)，
是仿射函數(shù)，并且不等式約束
，則存在
，使得
是原始問題的解，
是對偶問題的解（滿足這個條件的充分必要條件就是
滿足KKT條件1），并且：
引用
- 最優(yōu)化問題學習筆記1-對偶理論 CSDN
- 《統(tǒng)計學習方法》 豆瓣
- 如何理解對偶問題？ feng liu的回答
- 《拉格朗日乘數(shù)法和KKT條件的直觀解釋》 CSDN
- SVM的拉格朗日函數(shù)表示以及其對偶問題 CSDN