淺談最優化問題的KKT條件

01-24

最近學習了最優化理論，正好學到了機器學習中支持向量機（Support Vector Machine）和最大熵模型（Maximum Entropy Model）中用到的KKT條件（Karush–Kuhn–Tucker conditions）.

之前看了一些相關書籍，發現KKT條件的證明不是有些簡略，就是太偏「數學」（對於非數學專業的學生可能看不懂）——不適合非數學專業的同學入門. 因此我通過總結教材、上課筆記和加入一些幫助理解的重要註記（個人認為不「顯然」的內容），寫下這篇文章，供大家學習和交流！

PS：知乎的排版有些亂，望看官們不要介意：）

0.什麼是KKT條件

1.等式約束優化問題（Lagrange乘數法）
2.不等式約束優化問題
3.總結

0.什麼是KKT條件

本文從本科高數（微積分）中的有條件極值的Lagrange乘數法入手，一步步推導到KKT條件. 但在講述推導過程之前，我想先給出KKT條件：

對於具有等式和不等式約束的一般優化問題

$[egin{array}{l}min { m{ }}f({f{x}})\s.t.{ m{ }}{g_j}({f{x}}) le 0(j = 1,2, cdots ,m)\{ m{ }}{h_k}({f{x}}) = 0(k = 1,2, cdots ,l)end{array}]$

KKT條件給出了判斷 $[{{f{x}}^*}]$ 是否為最優解的必要條件，即：

$[left{ egin{array}{l}frac{{partial f}}{{partial {x_i}}} + sumlimits_{j = 1}^m {{mu _j}} frac{{partial {g_j}}}{{partial {x_i}}} + sumlimits_{k = 1}^l {{lambda _k}frac{{partial {h_k}}}{{partial {x_i}}}} = 0,{ m{ }}left( {i = 1,2,...,n} ight)\{h_k}left( {f{x}} ight) = 0,{ m{ (}}k = 1,2, cdots ,l)\{mu _j}{g_j}left( {f{x}} ight) = 0,{ m{ (}}j = 1,2, cdots ,m)\{mu _j} ge 0.end{array} ight.]$

1. 等式約束優化問題（Lagrange乘數法）

對於這部分內容，其實本科高數課程中已學過，因此本文直接給出結論，並補充一些我的理解與總結，它能幫助理解不等式約束中的一些內容，具體的推導過程在同濟7版的高數下冊（P.116-118）中已寫的較詳細。

所謂的等式約束優化問題是指

$minf(x_{1} ,x_{2} ,...,x_{n} )$

$s.t.h_{k} (x_{1} ,x_{2} ,...,x_{n} )=0$

我們令 $[L({f{x}},{f{lambda }}) = f({f{x}}) + sumlimits_{k = 1}^l {{lambda _k}{h_k}({f{x}})} ]$ ，函數 $L(x,y)$ 稱為Lagrange函數，參數 $lambda$ 稱為Lagrange乘子.

再聯立方程組： $[left{ egin{array}{l}frac{{partial L}}{{partial {x_i}}} = 0{ m{ ( }}i{ m{ = 1 ,2 ,}} cdots { m{,}}n{ m{ ) }}\frac{{partial L}}{{partial {lambda _k}}} = 0{ m{ ( }}k{ m{ = 1 ,2 ,}} cdots { m{,}}l{ m{ ) }}end{array} ight.]$ ，

得到的解為可能極值點，由於我們用的是必要條件，具體是否為極值點需根據問題本身的具體情況檢驗. 這個方程組稱為等式約束的極值必要條件.

上式我們對 $n$ 個 $x_{i}$ 和 $l$ 個 $lambda _{k}$ 分別求偏導，回想一下在無約束優化問題 $f(x_{1}, x_{2},...,x_{n} )=0$ 中，我們根據極值的必要條件，分別令 $frac{partial f}{partial x_{i} } =0$ ，求出可能的極值點. 因此可以聯想到：等式約束下的Lagrange乘數法引入了 $l$ 個Lagrange乘子，或許我們可以把 $lambda _{k}$ 也看作優化變數（ $x_{i}$ 就叫做優化變數）. 相當於將優化變數個數增加到 $(n+l)$ 個， $x_{i}$ 與 $lambda _{k}$ 一視同仁，均為優化變數，均對它們求偏導.

2. 不等式約束優化問題

以上我們討論了等式約束的情形，接下來我們來介紹不等式約束的優化問題.我們先給出其主要思想：轉化的思想——將不等式約束條件變成等式約束條件.具體做法：引入鬆弛變數.鬆弛變數也是優化變數，也需要一視同仁求偏導.

具體而言，我們先看一個一元函數的例子： $minf(x)$

$s.t. g_{1}(x) =a-xleq 0 \g_{2}(x) =x-bleq 0$

（註：優化問題中，我們必須求得一個確定的值，因此不妨令所有的不等式均取到等號，即 $leq$ 的情況.）

對於約束 $g_{1}$ 和 $g_{2}$ ，我們分別引入兩個鬆弛變數 $a_{1}^{2}$ 和 $b_{1}^{2}$ ，得到 $h_{1} (x,a_{1} )=g_{1} +a_{1}^{2} =0$ 和 $h_{2} (x,b_{1} )=g_{2} +b_{1}^{2} =0$ .注意，這裡直接加上平方項 $a_{1}^{2}$ 、 $b_{1}^{2}$ 而非 $a_{1}$ 、 $b_{1}$ ，是因為 $g_{1}$ 和 $g_{2}$ 這兩個不等式的左邊必須加上一個正數才能使不等式變為等式.若只加上 $a_{1}$ 和 $b_{1}$ ，又會引入新的約束 $a_{1} geq 0$ 和 $b_{1} geq 0$ ，這不符合我們的意願.

由此我們將不等式約束轉化為了等式約束，並得到Lagrange函數

$L(x,a_{1} ,b_{1} ,mu _{1} ,mu _{2} )=f(x)+mu _{1}(a-x+a_{1}^{2} )+mu _{2}(x-b+b_{1}^{2} )$

我們再按照等式約束優化問題（極值必要條件）對其求解，聯立方程

（註：這裡的 $mu _{1} geq 0$ ， $mu _{2} geq 0$ 先承認，我們待會再解釋！（先上車再買票，手動斜眼）實際上對於不等式約束前的乘子，我們要求其大於等於0）

得出方程組後，便開始動手解它. 看到第3行的兩式 $mu _{1} a_{1} =0$ 和 $mu _{1} a_{1} =0$ 比較簡單，我們就從它們入手吧~

對於 $mu _{1} a_{1} =0$ ，我們有兩種情況：

情形1： $mu _{1} =0,a_{1} e 0$

此時由於乘子 $mu _{1} =0$ ，因此 $g_{1}$ 與其相乘為零，可以理解為約束 $g_{1}$ 不起作用，且有 $g_{1}(x) =a-x< 0$ .

情形2： $mu _{1} geq 0,a_{1} =0$

此時 $g_{1}(x) =a-x= 0$ 且 $mu _{1} > 0$ ，可以理解為約束 $g_{1}$ 起作用，且有 $g_{1}(x)=0$ .

合併情形1和情形2得： $mu _{1}g_{1}=0$ ，且在約束起作用時 $mu _{1} > 0$ ， $g_{1}(x)=0$ ；約束不起作用時 $mu _{1}=0$ ， $g_{1}(x)<0$ .

同樣地，分析 $mu _{2}b_{1}=0$ ，可得出約束 $g_{2}$ 起作用和不起作用的情形，並分析得到 $mu _{2}g_{2}=0$ .

由此，方程組（極值必要條件）轉化為

$[left{ egin{array}{l}frac{{df}}{{dx}} + {mu _1}frac{{d{g_1}}}{{dx}} + {mu _2}frac{{d{g_2}}}{{dx}} = 0,\{mu _1}{g_1}left( x ight) = 0,{mu _2}{g_2}left( x ight) = 0,\{mu _1} ge 0,{mu _2} ge 0.end{array} ight.]$

這是一元一次的情形.類似地，對於多元多次不等式約束問題

$[egin{array}{l}min { m{ }}f({f{x}})\s.t.{ m{ }}{g_j}({f{x}}) le 0{ m{ }}(j = 1,2, cdots ,m)end{array}]$

我們有

$[left{ egin{array}{l}frac{{partial fleft( {{x^*}} ight)}}{{partial {x_i}}} + sumlimits_{j = 1}^m {{mu _j}frac{{partial {g_j}left( {{x^*}} ight)}}{{partial {x_i}}}} = 0{ m{ }}left( {i = 1,2,...,n} ight),\{mu _j}{g_j}left( {{x^*}} ight) = 0{ m{ }}left( {j = 1,2,...,m} ight),\{mu _j} ge 0{ m{ }}left( {j = 1,2,...,m} ight).end{array} ight.]$

上式便稱為不等式約束優化問題的KKT（Karush-Kuhn-Tucker）條件. $mu _{j}$ 稱為KKT乘子，且約束起作用時 $mu _{j}geq 0$ ， $g_{j}(x)=0$ ；約束不起作用時 $mu _{j}= 0$ ， $g_{j}(x)<0$ .

別急，還木有完，我們還剩最後一個問題沒有解決：為什麼KKT乘子必須大於等於零——我將用幾何性質來解釋.

由於

$[frac{{partial fleft( {{x^*}} ight)}}{{partial {x_i}}} + sumlimits_{j = 1}^m {{mu _j}frac{{partial {g_j}left( {{x^*}} ight)}}{{partial {x_i}}}} = 0{ m{ }}left( {i = 1,2,...,n} ight)]$

用梯度表示： $[ abla fleft( {{{f{x}}^*}} ight) + sumlimits_{j in J} {{mu _j} abla {g_j}left( {{{f{x}}^*}} ight)} = 0]$ ， $J$ 為起作用約束的集合.

移項： $[ - abla fleft( {{{f{x}}^*}} ight) = sumlimits_{j in J} {{mu _j} abla {g_j}left( {{{f{x}}^*}} ight)} ,]$

注意到梯度為向量. 上式表示在約束極小值點 $[{{f{x}}^*}]$ 處，函數 $[fleft( {{{f{x}}^*}} ight)]$ 的負梯度一定可以表示成：所有起作用約束在該點的梯度（等值線的法向量）的線性組合.（複習課本中梯度的性質：某點梯度的方向就是函數等值線 $[f({f{x}}) = C]$ 在這點的法線方向，等值線就是地理的等高線）

為方便作圖，假設現在只有兩個起作用約束，我們作出圖形如下圖.注意我們上面推導過，約束起作用時 $[{g_j}left( {f{x}} ight) = 0]$ ，所以此時約束在幾何上應該是一簇約束平面.我們假設在 $[{{f{x}}^*}]$ 取得極小值點，若同時滿足 $[{g_1}left( {f{x}} ight) = 0]$ 和 $[{g_2}left( {f{x}} ight) = 0]$ ，則 $[{{f{x}}^k}]$ 一定在這兩個平面的交線上，且 $[ - abla fleft( {{{f{x}}^*}} ight) = sumlimits_{j in J} {{mu _j} abla {g_j}left( {{{f{x}}^*}} ight)} ]$ ，即 $[ - abla fleft( {{{f{x}}^k}} ight)]$ 、 $[ abla {g_1}left( {{{f{x}}^k}} ight)]$ 和 $[ abla {g_2}left( {{{f{x}}^k}} ight)]$ 共面.

下圖是在點 $[{{f{x}}^k}]$ 處沿 $x_{1}Ox_{2}$ 面的截面，過點 $[{{f{x}}^k}]$ 作目標函數的負梯度 $[ - abla fleft( {{{f{x}}^k}} ight)]$ ，它垂直於目標函數的等值線 $[f({f{x}}) = C]$ （高數課本：一點的梯度與等值線相互垂直），且指向目標函數 $[f({f{x}}) ]$ 的最速減小方向.再作約束函數 $[{g_1}left( {f{x}} ight) = 0]$ 和 $[{g_2}left( {f{x}} ight) = 0]$ 的梯度 $[ abla {g_1}left( {{{f{x}}^k}} ight)]$ 和 $[ abla {g_2}left( {{{f{x}}^k}} ight)]$ ，它們分別垂直 $[{g_1}left( {f{x}} ight) = 0]$ 和 $[{g_2}left( {f{x}} ight) = 0]$ 兩曲面在 $[{{f{x}}^k}]$ 的切平面，並形成一個錐形夾角區域.此時，可能有a、b兩種情形：

我們先來看情形b：若3個向量的位置關係如b所示，即 $[ - abla f]$ 落在 $[ abla {g_1}]$ 和 $[ abla {g_2}]$ 所形成的錐角區外的一側. 此時，作等值面 $[f({f{x}}) = C]$ 在點 $[{{f{x}}^k}]$ 的切平面（它與 $[ - abla fleft( {{{f{x}}^k}} ight)]$ 垂直），我們發現：沿著與負梯度 $[ - abla f]$ 成銳角的方向移動（如下圖紅色箭頭方向），只要在紅色區域取值，目標函數 $[f({f{x}}) ]$ 總能減小.而紅色區域是可行域（ $[f({f{x}}) = C]$ ，C取不同的常數能得到不同的等值線，因此能取到紅色區域），因此既可減小目標函數值，又不破壞約束條件. 這說明 $[{{f{x}}^k}]$ 仍可沿約束曲面移動而不破壞約束條件，且目標函數值還能夠減小.所以 $[{{f{x}}^k}]$ 不是穩定的最優點，即不是局部極值點.

反過頭來看情形a： $[ - abla f]$ 落在 $[ abla {g_1}]$ 和 $[ abla {g_2}]$ 形成的錐角內. 此時，同樣作 $[f({f{x}}) = C]$ 在點 $[{{f{x}}^k}]$ 與 $[ - abla f]$ 垂直的切平面. 當從 $[{{f{x}}^k}]$ 出發沿著與負梯度 $[ - abla f]$ 成銳角的方向移動時，雖然能使目標函數值減小，但此時任何一點都不在可行區域內. 顯然，此時 $[{{f{x}}^k}]$ 就是局部最優點 $[{{f{x}}^*}]$ ，再做任何移動都將破壞約束條件，故它是穩定點.

由於 $[ - abla fleft( {{{f{x}}^*}} ight)]$ 和 $[ abla g_{1}left( {{{f{x}}^*}} ight)]$ 、 $[ abla g_{2}left( {{{f{x}}^*}} ight)]$ 在一個平面內，所以前者可看成是後兩者的線性組合. 又由上面的幾何分析知， $[ - abla fleft( {{{f{x}}^*}} ight)]$ 在 $[ abla g_{1}left( {{{f{x}}^*}} ight)]$ 和 $[ abla g_{2}left( {{{f{x}}^*}} ight)]$ 的夾角之間，所以線性組合的係數為正，有

$[ - abla fleft( {{{f{x}}^*}} ight){ m{ = }}{mu _{ m{1}}} abla {g_{ m{1}}}left( {{{f{x}}^*}} ight){ m{ + }}{mu _{ m{2}}} abla {g_{ m{2}}}left( {{{f{x}}^*}} ight)]$ ，且 $mu _{1}>0$ ， $mu _{2}>0$ .

這就是 $mu _{j}>0$ 的原因. 類似地，當有多個不等式約束同時起作用時，要求 $[ - abla fleft( {{{f{x}}^*}} ight)]$ 處於 $[ abla g_{j}left( {{{f{x}}^*}} ight)]$ 形成的超角錐（高維圖形，我姑且稱之為「超」）之內.

3.總結：同時包含等式和不等式約束的一般優化問題

$[egin{array}{l}min { m{ }}f({f{x}})\s.t.{ m{ }}{g_j}({f{x}}) le 0(j = 1,2, cdots ,m)\{ m{ }}{h_k}({f{x}}) = 0(k = 1,2, cdots ,l)end{array}]$

KKT條件（ $[{{f{x}}^*}]$ 是最優解的必要條件）為

注意，對於等式約束的Lagrange乘子，並沒有非負的要求！以後求其極值點，不必再引入鬆弛變數，直接使用KKT條件判斷！

這樣，我們就推導完了KKT條件。各位看官可以自己分別羅列並比較一下：無約束優化、等式約束優化和等式+不等式約束優化條件下某點為局部最優解（極值點）的必要條件。

如果對於Lagrange對偶性感興趣的同學，可以進一步地研究下去，這樣才能較深入地掌握SVM，本人也在學習中，歡迎交流~