本文轉(zhuǎn)自徐飛翔的“《SVM筆記系列之三》拉格朗日乘數(shù)法和KKT條件的直觀解釋”
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明。
最優(yōu)化問題
我們在高中，包括在高數(shù)中都會經(jīng)常遇到求解一個函數(shù)的最小值，最大值之類的問題，這類問題就是屬于最優(yōu)化問題。比如給出下列一個不帶有約束的最優(yōu)化問題：
其中的我們稱為目標(biāo)函數(shù)(objective function)。這樣的問題，直接利用**羅爾定理（Rolle’s theorem）**求出其鞍點(diǎn)，又因?yàn)槠錇橥购瘮?shù)而且可行域是整個
，求出的鞍點(diǎn)便是最值點(diǎn)，這個是對于無約束最優(yōu)化問題的解題套路。如果問題帶有約束條件，那么就變得不一樣了，如：
因?yàn)榇藭r(shí)的約束條件是仿射函數(shù)（affine function）1，所以可以利用換元法將X表示為Y的函數(shù)，從而將目標(biāo)函數(shù)變?yōu)闊o約束的形式，然后利用羅爾定理便可以求出最值點(diǎn)了。然而如果約束條件一般化為，那么X就不一定可以用其他變量表示出來了，這個時(shí)候就要利用 拉格朗日乘數(shù)法(Lagrange multipliers ) 了。
拉格朗日乘數(shù)法(Lagrange multipliers)我們先一般化一個二元最優(yōu)化問題為( 2.1 ) 形式：
將目標(biāo)函數(shù)和等式約束條件
畫出來就如下圖所示：
其中的虛線為等高線，而紅線為
這個約束函數(shù)曲線與
的交點(diǎn)的連線在
平 面 映射。其中，假設(shè)有
? ，
點(diǎn)為最小值點(diǎn)（最優(yōu)值點(diǎn)）。從直觀上可以發(fā)現(xiàn)，在
與
的非最優(yōu)化交點(diǎn)A,B,C,D上，其
和
的法線方向并不是共線的，注意，這個相當(dāng)關(guān)鍵，因?yàn)槿绻皇枪簿€的，說明
與
的交點(diǎn)中，還存在可以取得更小值的點(diǎn)存在。對于A點(diǎn)來說，B點(diǎn)就是更為小的存在。因此，我們從直覺上推論出只有當(dāng)
與
的法線共線時(shí)，才是最小值點(diǎn)的候選點(diǎn)（鞍點(diǎn)）。推論到多元變量的問題的時(shí)候，法線便用梯度表示。于是，我們有原問題取得最優(yōu)值的必要條件：
(2.2)其中的表示兩個梯度共線。可以簡單的變形為：
讓我們?nèi)サ籼荻人阕?，得?/span>
這個時(shí)候取個負(fù)號也是不影響的，所以式子(2.4)通常寫作：
看！我們得出了我們高數(shù)中經(jīng)常見到的等式約束下的拉格朗日乘數(shù)函數(shù)的表示方法。
以上，我們討論的都是單約束的拉格朗日乘數(shù)法，當(dāng)存在多個等式約束時(shí)（其實(shí)不等式約束也是一樣的），我們進(jìn)行一些推廣。先一般化一個二元多約束最小化問題：
對于每個目標(biāo)函數(shù)和約束配對，我們有:
將上式相加有：
定義多約束的拉格朗日函數(shù)為：
因?yàn)?lambda;是常數(shù)，表示共線的含義而已，所以乘上一個常數(shù)
也不會有任何影響，我們?nèi)匀挥?span>
表示，因此式子( 2.8 ) 變成：
這就是多約束拉格朗日乘數(shù)法的函數(shù)表達(dá)形式。
讓我們舉一個單約束的拉格朗日乘數(shù)法的計(jì)算例子，例子來源于引用3。給出一個最大化任務(wù)：
圖像如：
只有一個約束，使用一個乘子，有拉格朗日函數(shù)：
按照條件求解候選點(diǎn)：
有
根據(jù)式子( i ) ( i i ) ( i i i ) ， 解得有：
代入f ( x , y )，得到：2， -2， 0，也就是我們需要求得的最大值，最小值?？梢詮膱D中看出，我們觀察到其等高線與約束投影線的確是相切的。
廣義拉格朗日乘數(shù)法(Generalized Lagrange multipliers)上面我們的拉格朗日乘數(shù)法解決了等式約束的最優(yōu)化問題，但是在存在不等式約束的最優(yōu)化問題（包括我們SVM中需要求解的最優(yōu)化問題）上，普通的拉格朗日乘數(shù)法并不能解決，因此學(xué)者提出了廣義拉格朗日乘數(shù)法（Generalized Lagrange multipliers）， 用于解決含有不等式約束的最優(yōu)化問題。這一章，我們談一談廣義拉格朗日乘數(shù)法。
首先，我們先一般化我們的問題，規(guī)定一個二元標(biāo)準(zhǔn)的帶有不等式約束的最小化問題(當(dāng)然可以推廣到多元的問題)，如：
類似于拉格朗日乘數(shù)法，參照式子( 2.9 ) ，我們使用和
作為等式約束和不等式約束的拉格朗日乘子，得出下式：
KKT條件（Karush–Kuhn–Tucker conditions） 指出，當(dāng)滿足以下幾個條件的時(shí)候，其解是問題最優(yōu)解的候選解(摘自wikipedia)。
Stationarity
對于最小化問題就是：
對于最大化問題就是：
Primal feasibility
Dual feasibility
Complementary slackness
其中的第一個條件和我們的拉格朗日乘數(shù)法的含義是相同的，就是梯度共線的意思；而第二個條件就是主要約束條件，自然是需要滿足的；有趣的和值得注意的是第三個和第四個條件，接下來我們探討下這兩個條件，以及為什么不等式約束會多出這兩個條件。
為了接下來的討論方便，我們將N設(shè)為3，并且去掉等式約束，這樣我們的最小化問題的廣義拉格朗日函數(shù)就變成了：
繪制出來的示意圖如下所示：
其中，而藍(lán)線為最優(yōu)化尋路過程。
讓我們仔細(xì)觀察式子( 3.7 )和( 3.8 )，我們不難發(fā)現(xiàn)，因?yàn)?span>而
，并且需要滿足
，所以
和
之中必有一個為0，那為什么會這樣呢？
我們從上面的示意圖入手理解并且記好公式( 3.3 )。讓我們假設(shè)初始化一個點(diǎn)A， 這個點(diǎn)A明顯不處于最優(yōu)點(diǎn)，也不在可行域內(nèi)，可知違背了( 3.5 ) ，為了滿足約束( 3.8 ) ，有
，導(dǎo)致
，而對于
，因?yàn)闈M足約束條件而且
，所以
。這樣我們的式子( 3.3 )就只剩下
，因此對著
進(jìn)行優(yōu)化，也就是沿著
梯度方向下降即可，不需考慮其他的條件（因?yàn)檫€完全處于可行域之外）。因此，A點(diǎn)一直走啊走，從A到B，從B到C，從C到D，這個時(shí)候因?yàn)镈點(diǎn)滿足
，因此
，所以
，因此( 3.3 ) 就變成了
所以在優(yōu)化下一個點(diǎn)E的時(shí)候，就會考慮到需要滿足約束
的條件，朝著向
減小，而且
減小的方向優(yōu)化。因此下一個優(yōu)化點(diǎn)就變成了E點(diǎn)，而不是G點(diǎn)。因此沒有約束的情況下其優(yōu)化路徑可能是
，而添加了約束之后，其路徑變成了
。
這就是為什么KKT條件引入了條件3和條件4，就是為了在滿足不等式約束的情況下對目標(biāo)函數(shù)進(jìn)行優(yōu)化。讓我們記住這個條件，因?yàn)檫@個條件中某些的特殊性質(zhì)，將會在SVM中廣泛使用，而且正是這個性質(zhì)定義了支持向量(SV)。
Q & A
這里回答下知乎的朋友的一些問題，鏈接為：《SVM筆記系列之三》拉格朗日乘數(shù)法和KKT條件的直觀解釋。主要有兩個問題。
-
戰(zhàn)勝： 最開始分析你說g1，g3都非零，所以α1=0，α3=0；照你這么分析的話，后面的3個不等式項(xiàng)都是零呀，都是無約束了！
A：因?yàn)樵贏，B，C點(diǎn)時(shí)處在可行域之外，因此所有的都為0，這個保證了在可行域之外會按照
的梯度方向進(jìn)行優(yōu)化，而不需要考慮其他約束。這就退化到了一般的無約束優(yōu)化了。這個也是可以理解的，畢竟在可行域之外為什么需要考慮約束的作用呢？
2. 安夢徒生: 看不懂為什么往E的方向
A: 在D這個點(diǎn)剛好到可行域的邊界，因此按照上面的分析，梯度方向應(yīng)該是，因此應(yīng)該是
和
梯度方向的合成，而不單是某個約束函數(shù)的梯度方向。我這里假設(shè)他的合成梯度方向到達(dá)的點(diǎn)是E點(diǎn)作為示例而已。
引用
拉格朗日乘子法如何理解？ 知乎
《統(tǒng)計(jì)學(xué)習(xí)方法》 豆瓣
《【直觀詳解】拉格朗日乘法和KKT條件》 微信公眾號
《解密SVM系列（一）：關(guān)于拉格朗日乘子法和KKT條件》 CSDN
Karush–Kuhn–Tucker conditions wikipedia
最高次數(shù)為1的多項(xiàng)式，形如，其中X 是
的仿射矩陣，其與線性函數(shù)的區(qū)別就是，線性函數(shù)是
沒有偏置項(xiàng)B。