《SVM筆記系列之三》拉格朗日乘數法和KKT條件的直觀解釋

徐土豆 2022-03-31 10:54 791 閱讀 2 贊 1 收藏 0 評論

本文轉自徐飛翔的“《SVM筆記系列之三》拉格朗日乘數法和KKT條件的直觀解釋”

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

最優化問題

我們在高中，包括在高數中都會經常遇到求解一個函數的最小值，最大值之類的問題，這類問題就是屬于最優化問題。比如給出下列一個不帶有約束的最優化問題：

其中的我們稱為目標函數(objective function)。這樣的問題，直接利用**羅爾定理（Rolle’s theorem）**求出其鞍點，又因為其為凸函數而且可行域是整個，求出的鞍點便是最值點，這個是對于無約束最優化問題的解題套路。如果問題帶有約束條件，那么就變得不一樣了，如：

因為此時的約束條件是仿射函數（affine function）1，所以可以利用換元法將X表示為Y的函數，從而將目標函數變為無約束的形式，然后利用羅爾定理便可以求出最值點了。然而如果約束條件一般化為，那么X就不一定可以用其他變量表示出來了，這個時候就要利用拉格朗日乘數法(Lagrange multipliers ) 了。

拉格朗日乘數法(Lagrange multipliers)我們先一般化一個二元最優化問題為( 2.1 ) 形式：

將目標函數和等式約束條件畫出來就如下圖所示：

其中的虛線為等高線，而紅線為這個約束函數曲線與的交點的連線在平面映射。其中，假設有? ，點為最小值點（最優值點）。從直觀上可以發現，在與的非最優化交點A,B,C,D上，其和的法線方向并不是共線的，注意，這個相當關鍵，因為如果不是共線的，說明與的交點中，還存在可以取得更小值的點存在。對于A點來說，B點就是更為小的存在。因此，我們從直覺上推論出只有當與的法線共線時，才是最小值點的候選點（鞍點）。推論到多元變量的問題的時候，法線便用梯度表示。于是，我們有原問題取得最優值的必要條件：

(2.2)其中的 $\lambda$ 表示兩個梯度共線。可以簡單的變形為：

讓我們去掉梯度算子，得出

這個時候 $\lambda$ 取個負號也是不影響的，所以式子(2.4)通常寫作：

看！我們得出了我們高數中經常見到的等式約束下的拉格朗日乘數函數的表示方法。

多約束的拉格朗日乘數法

以上，我們討論的都是單約束的拉格朗日乘數法，當存在多個等式約束時（其實不等式約束也是一樣的），我們進行一些推廣。先一般化一個二元多約束最小化問題：

對于每個目標函數和約束配對，我們有:

將上式相加有：

定義多約束的拉格朗日函數為：

因為λ $\lambda_i$ 是常數，表示共線的含義而已，所以乘上一個常數 $\frac{1}{N}$ 也不會有任何影響，我們仍然用 $\lambda_i$ 表示，因此式子( 2.8 ) 變成：

這就是多約束拉格朗日乘數法的函數表達形式。

一個計算例子

讓我們舉一個單約束的拉格朗日乘數法的計算例子，例子來源于引用3。給出一個最大化任務：

圖像如：

只有一個約束，使用一個乘子 $\lambda$ ，有拉格朗日函數：

按照條件求解候選點：

有

根據式子( i ) ( i i ) ( i i i ) ，解得有：

代入f ( x , y )，得到：2， -2， 0，也就是我們需要求得的最大值，最小值。可以從圖中看出，我們觀察到其等高線與約束投影線的確是相切的。

廣義拉格朗日乘數法(Generalized Lagrange multipliers)上面我們的拉格朗日乘數法解決了等式約束的最優化問題，但是在存在不等式約束的最優化問題（包括我們SVM中需要求解的最優化問題）上，普通的拉格朗日乘數法并不能解決，因此學者提出了廣義拉格朗日乘數法（Generalized Lagrange multipliers），用于解決含有不等式約束的最優化問題。這一章，我們談一談廣義拉格朗日乘數法。

首先，我們先一般化我們的問題，規定一個二元標準的帶有不等式約束的最小化問題(當然可以推廣到多元的問題)，如：

類似于拉格朗日乘數法，參照式子( 2.9 ) ，我們使用 $\alpha_i$ 和 $\beta_i$ 作為等式約束和不等式約束的拉格朗日乘子，得出下式：

KKT條件（Karush–Kuhn–Tucker conditions）指出，當滿足以下幾個條件的時候，其解是問題最優解的候選解(摘自wikipedia)。

Stationarity

對于最小化問題就是：

對于最大化問題就是：

Primal feasibility

Dual feasibility

Complementary slackness

其中的第一個條件和我們的拉格朗日乘數法的含義是相同的，就是梯度共線的意思；而第二個條件就是主要約束條件，自然是需要滿足的；有趣的和值得注意的是第三個和第四個條件，接下來我們探討下這兩個條件，以及為什么不等式約束會多出這兩個條件。

為了接下來的討論方便，我們將N設為3，并且去掉等式約束，這樣我們的最小化問題的廣義拉格朗日函數就變成了：

繪制出來的示意圖如下所示：

其中，而藍線為最優化尋路過程。

讓我們仔細觀察式子( 3.7 )和( 3.8 )，我們不難發現，因為 $a_i \geq 0$ 而 $g_i(x, y) \leq 0$ ，并且需要滿足，所以和之中必有一個為0，那為什么會這樣呢？

我們從上面的示意圖入手理解并且記好公式( 3.3 )。讓我們假設初始化一個點A，這個點A明顯不處于最優點，也不在可行域內，可知違背了( 3.5 ) ，為了滿足約束( 3.8 ) ，有，導致 $a_2 \nabla g_2(x,y)=0$ ，而對于，因為滿足約束條件而且 $g_1(x,y) \neq 0, g_3(x,y) \neq 0$ ，所以 $a_1 = 0, \alpha_3 = 0$ 。這樣我們的式子( 3.3 )就只剩下 $\nabla f(x,y)$ ，因此對著 $\nabla f(x,y)$ 進行優化，也就是沿著梯度方向下降即可，不需考慮其他的條件（因為還完全處于可行域之外）。因此，A點一直走啊走，從A到B，從B到C，從C到D，這個時候因為D點滿足，因此，所以 $\nabla g_2(x,y) \neq 0$ ，因此( 3.3 ) 就變成了 $\nabla f(x,y)+\alpha_2\nabla g_2(x,y)$ 所以在優化下一個點E的時候，就會考慮到需要滿足約束 $g_2(x,y) \leq 0$ 的條件，朝著向減小，而且減小的方向優化。因此下一個優化點就變成了E點，而不是G點。因此沒有約束的情況下其優化路徑可能是 $A \rightarrow B \rightarrow C \rightarrow D \rightarrow G \rightarrow H$ ，而添加了約束之后，其路徑變成了 $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F$ 。