通俗易懂 | SVM之拉格朗日乘子法

在SVM中，將約束問題轉化成非約束問題採用到了拉格朗日乘子法。這個文章就講一下拉格朗日乘子法與KKT約束是怎麼回事。本人不是數學科班出身，但是也只能硬著頭皮講一講了。

從零理解

現在我們要解決這樣一個問題：這個函數距離原點最近的距離是多少。

先畫出函數圖像：

然後想求出最短距離：

這裡的思路就是，做一個以原點為中心的圓形：

不斷擴大圓形的半徑，直到圓與藍色的曲線相切：

現在。第一次與

這個，圓形與曲線相切，且切線既是圓形的切線，也是曲線的相切。

這時候，這個切線的垂線其實也就是我們所說的梯度，也叫做等高線的法線，看下面兩個圖可能會好理解一些：

那麼這個梯度怎麼計算呢？先看圓形

再看曲線的梯度計算

在相切的時候，兩者的梯度方向都在同一條直線上，可以稱之為，成比例，這裡用比例係數

所以我們匯總一下所有的已知信息，得到下面的方程組：

可以求解得到：

這個就是拉格朗日乘子法的直觀理解。

抽象成數學的形式

我們要解決的問題：

我們會將約束問題通過拉格朗日乘子法轉換成非約束問題：

【為什麼可以這樣呢？】如果求極值，偏導數為0。先對上面的公式進行求偏導數：

這兩個等式與這個等價，唯一的不同就是

當然，對於

KKT條件KKT的英文全稱：Karush-Kuhn-Tucker

之前的拉格朗日的約束條件是等值的，現在可以通過KKT條件推廣到不等式。因為限制條件往往是不大於，小於這樣的不等式，所以KKT才是拉格朗日化約束問題為非約束問題的關鍵。

對於不等式問題，就是有兩種情況：

可行解在g(x)<0，就表示這個約束條件並沒有起到約束效果，有跟沒有是一個效果（下圖中的左圖）；可行解g(x)=0,就表示這個約束條件起到作用了，這就表示g(x)與f(x)相切，也就是下圖中右邊的圖。

【g(x)<0的情況】這種情況下，就是沒有限制條件下的情況，其實就是沒有約束條件的限制，也就是

【g(x)=0的情況】如果是g(x)=0的情況，那也就是約束條件起到作用了，也就意味著

所以綜上所述，在這種情況下，我們所有的條件綜合起來可以得到，其中

這三個就是KKT條件。