支持向量機(SVM)（二）-- 拉格朗日對偶（Lagrange duality）

簡介：

1、在之前我們把要尋找最優的分割超平面的問題轉化為帶有一系列不等式約束的優化問題。這個最優化問題被稱作原問題。我們不會直接解它，而是把它轉化為對偶問題進行解決。

2、為了使問題變得易于處理，我們的方法是把目標函數和約束全部融入一個新的函數，為了使問題變得易于處理，我們的方法是把目標函數和約束全部融入一個新的函數，即拉格朗日函數，再通過這個函數來尋找最優點。即拉格朗日函數，再通過這個函數來尋找最優點。

3、約束條件可以分成不等式約束條件和等式約束條件，只有等式約束條件的問題我們在高等數學課程中已經學習過了，其解決方法是直接將等式約束加入原問題構造出拉格朗日函數，然后求導即可。現在考慮更加一般性的問題：帶不等式約束和等式約束的極值問題如何構造拉格朗日函數求解。
學習拉格朗日對偶原理重要的是理解構造所得的原始問題和原函數的等價性，以及原始問題和對偶問題解得等價性。

回憶一下之前得到的目標函數

1、我們下看下面的一個式子

上面是要求解的目標函數及其條件。我們可以得到拉格朗日公式為

在這里被稱為拉格朗日算子。

然后分別對w和求偏導，使得偏導數等于0，然后解出和；

下面我們將要產生一個既有等式又有不等式條件限制的式子，我們可以叫做原始優化問題，這里簡單介紹下拉格朗日對偶的原理。如下式子：

上述式子有兩個條件（等式條件和不等式條件）

由此我們定義一般化的拉格朗日公式

這里的和都是拉格朗日算子。不要忘了我們求解的是最小值。

設如下等式：

這里的P代表primal。我們設如下約束條件（primal constraints）：

如果條件不全部滿足的話，我們總可以調整和使最大值出現正無窮，即會出現下面情況：

因此我們可以得出如下式子：

這樣我們原來要求的min f(w)可以轉換成求了。

同時我們設

將問題轉化為先求拉格朗日關于的最小值，這個時候就把和看做常量。之后再求最大值。

如下：

這個問題就是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結果是Max Min(X) <= Min Max(X)。然而在這里兩者相等。由此我們可以設如下：

所以在一定的條件下我們可以得到：

因此我們可以解決原問題的對偶問題，但是我們還要看看條件是什么。

假設f和g都是凸函數，h是仿射的(仿射的含義：存在ai, bi，使得)，并且還要滿足存在w使得所有的i都有；

有了以上的假設，那么一定會存在使得是原問題的解，是對偶問題的解。同時也滿足

另外，還滿足Karush-Kuhn-Tucker（ KKT condition），如下式子：

所以如果滿足了KKT條件，那么他們就是原問題和對偶問題的解。

我們從式子和式子可以看出如果那么，

這個也就說明時，w處于可行域的邊界上，這時才是起作用的約束。

而其他位于可行域內部的（）點都是不起作用的約束，其中也就是的時候。這個KKT雙重補足條件會用來解釋支持向量和SMO的收斂測試。

來自： http://blog.csdn.net//u011067360/article/details/25215465