拉格朗日对偶（转）
1.原始問題
假設是定義在上的連續可微函數（為什么要求連續可微呢，后面再說，這里不用多想），考慮約束最優化問題：
稱為約束最優化問題的原始問題。
現在如果不考慮約束條件，原始問題就是：
因為假設其連續可微，利用高中的知識，對求導數，然后令導數為0，就可解出最優解，很easy. 那么，問題來了（呵呵。。。），偏偏有約束條件，好煩啊，要是能想辦法把約束條件去掉就好了，bingo! 拉格朗日函數就是干這個的。
?
?
引進廣義拉格朗日函數（generalized Lagrange function）:
不要怕這個式子，也不要被拉格朗日這個高大上的名字給唬住了，讓我們慢慢剖析！這里，是拉格朗日乘子（名字高大上，其實就是上面函數中的參數而已），特別要求.
?
?
現在，如果把看作是關于的函數，要求其最大值，即
再次注意是一個關于的函數，經過我們優化（不要管什么方法），就是確定的值使得取得最大值（此過程中把看做常量），確定了的值，就可以得到的最大值，因為已經確定，顯然最大值就是只和有關的函數，定義這個函數為：
其中?
?
下面通過是否滿足約束條件兩方面來分析這個函數:
- 考慮某個違反了原始的約束，即或者，那么：
注意中間的最大化式子就是確定的之后的結果，若，則令，如果，很容易取值使得
?
- 考慮滿足原始的約束，則：，注意中間的最大化是確定的過程，就是個常量，常量的最大值顯然是本身.
?
通過上面兩條分析可以得出：
那么在滿足約束條件下：
即與原始優化問題等價,所以常用代表原始問題，下標 P 表示原始問題，定義原始問題的最優值：
?
?
原始問題討論就到這里，做一個總結：通過拉格朗日這位大神的辦法重新定義一個無約束問題（大家都喜歡無拘無束），這個無約束問題等價于原來的約束優化問題，從而將約束問題無約束化！
?
2.對偶問題
定義關于的函數：
注意等式右邊是關于的函數的最小化，確定以后，最小值就只與有關，所以是一個關于的函數.?
?
考慮極大化，即
這就是原始問題的對偶問題，再把原始問題寫出來：
形式上可以看出很對稱，只不過原始問題是先固定中的，優化出參數，再優化最優，而對偶問題是先固定，優化出最優，然后再確定參數.
定義對偶問題的最優值：
?
3. 原始問題與對偶問題的關系
定理：若原始問題與對偶問題都有最優值，則
證明：對任意的和，有
即
由于原始問題與對偶問題都有最優值，所以
即
也就是說原始問題的最優值不小于對偶問題的最優值，但是我們要通過對偶問題來求解原始問題，就必須使得原始問題的最優值與對偶問題的最優值相等，于是可以得出下面的推論：
推論：設分別是原始問題和對偶問題的可行解，如果，那么分別是原始問題和對偶問題的最優解。
所以，當原始問題和對偶問題的最優值相等：時，可以用求解對偶問題來求解原始問題（當然是對偶問題求解比直接求解原始問題簡單的情況下），但是到底滿足什么樣的條件才能使的呢，這就是下面要闡述的?KKT 條件
?
4. KKT 條件
定理：對于原始問題和對偶問題，假設函數和是凸函數，是仿射函數（即由一階多項式構成的函數，f(x)=Ax + b, A是矩陣，x，b是向量）；并且假設不等式約束是嚴格可行的，即存在，對所有有，則存在，使得是原始問題的最優解，是對偶問題的最優解，并且
?
?
定理：對于原始問題和對偶問題，假設函數和是凸函數，是仿射函數（即由一階多項式構成的函數，f(x)=Ax + b, A是矩陣，x，b是向量）；并且假設不等式約束是嚴格可行的，即存在，對所有有，則分別是原始問題和對偶問題的最優解的充分必要條件是滿足下面的Karush-Kuhn-Tucker(KKT)條件：
注意，下面的第四行使用了愛因斯坦求和約定，省略了Σ符號
關于KKT 條件的理解：前面三個條件是由解析函數的知識，對于各個變量的偏導數為0（這就解釋了一開始為什么假設三個函數連續可微，如果不連續可微的話，這里的偏導數存不存在就不能保證），后面四個條件就是原始問題的約束條件以及拉格朗日乘子需要滿足的約束。
特別注意當時，由KKT對偶互補條件可知：，這個知識點會在 SVM 的推導中用到.
?
5. 總結
一句話，某些條件下，把原始的約束問題通過拉格朗日函數轉化為無約束問題，如果原始問題求解棘手，在滿足KKT的條件下用求解對偶問題來代替求解原始問題，使得問題求解更加容易。
總結
- 上一篇： SVM基本思想及入门学习（转载+自己解释
- 下一篇： 用初中数学题理解SVM中不等式约束、拉格