非線性優化中的KKT條件該如何理解？

01-06

普通本科數學教中都會介紹Lagrange乘子法，用於求解帶等式約束的極值問題，KKT條件是拉格朗日乘子法的推廣，它的表述比較複雜，並不像拉格朗日法那樣被廣大本科生所了解。也許是因為出現在SVM模型的推導中，機器學習研究者倒是對其有所耳聞。

然而，KKT條件是一個具有很強幾何意義的結論，下面我們將給出這樣一個「直觀」的解釋。個人感覺它相當優美。

一、問題重述

KKT條件有幾個不同的等價表述方式，我們只討論其中一種，其他表述可以類似地推得。給定優化問題：

$max_{x}f(x) \s.t.h_j(x)=0,j=1,dots,q \g_i(x)leq 0,i=1,dots,p$

也就是說，自變數 $x$ 是一個n維向量，要最大化一個目標函數 $f$ ，滿足若干等式和不等式約束。KKT條件宣稱，如果有一個點 $x^*$ 是滿足所有約束的極值點，則

$abla f(x^*)=sum_jlambda_j abla h_j(x^*)+sum_imu_i abla g_i(x^*) \mu_igeq0,mu_ig_i(x^*)=0$

簡單說，就是在極值點處， $f$ 的梯度是一系列等式約束 $h_j$ 的梯度和不等式約束 $g_i$ 的梯度的線性組合。在這個線性組合中，等式約束梯度的權值 $lambda_j$ 沒有要求；不等式約束梯度的權值 $mu_i$ 是非負的，並且如果某個 $g_i(x^*)$ 嚴格小於0，那這個約束不會出現在加權式中，因為對應的權值 $mu_i$ 必須為0。換句話說，只有 $x^*$ 恰好在邊界 $g_i=0$ 上的那些 $g_i$ 的梯度才會出現在加權式中。如果去掉不等式約束的部分，那麼上式就是拉格朗日乘子法的精確表述。

二、理解思路

給定一個優化問題，我們把滿足所有約束條件的n維空間區域稱為可行域。從可行域中的每一個點 $x$ 朝某個方向 $v$ 出發走一點點，如果還在可行域中，或者偏離可行域的程度很小，準確地說，偏移量是行進距離的高階無窮小量，那麼我們就說 $v$ 是一個可行方向。我們用 $F(x)$ 表示點 $x$ 的所有可行方向的集合。

對於可行域中的一個極大值點 $x^*$ ，它的可行方向集合為 $F(x^*)$ ，從 $x^*$ 朝 $F(x^*)$ 中的某個方向走一小步，那麼落點仍然（近似）在可行域中。 $x^*$ 是局部最大值點就意味著在這些可行方向上目標函數 $f(x)$ 不能增大，從而我們得到下面這樣一個結論：

在極值點 $x^*$ ，讓目標函數增大的方向不能在 $F(x^*)$ 中。

把這句話精確表達出來，就得到了KKT條件的數學表述。

三、單約束的可行方向

滿足等式 $f(x)=0$ 的點 $x$ ，在n維空間里構成了一個(通常是光滑的)曲面，專業稱謂叫流形。這個曲面是n-1維的，因為自變數的n個分量只滿足一個方程，因而曲面上有n-1個自由度。例如在二維空間里 $y-x=0$ 是一條一維的直線，在三維空間中 $x^2+y^2+z^2-1=0$ 是一張二維曲面。

在這些曲面上每一點 $x$ 都存在一個梯度方向 $abla f(x)$ ，沿著這個方向函數值 $f(x)$ 增大，沿著它的逆方向 $- abla f(x)$ 函數值減小，這兩個方向我們記為

$N_f^+(x)={lambda abla f(x),lambdageq0}$

$N_f^-(x)={lambda abla f(x),lambdaleq0}$

$N_f = N_f^+cup N_f^-$

$N_f$ 是兩條射線的並，是由梯度方向張成的一維子空間。與這個一維子空間正交的n-1一維空間，被稱為切空間或者切平面 $T_f(x)$ ，自變數在 $T_f(x)$ 中的方向上移動時，函數值 $f$ 變化不大。我們都知道對於光滑的曲面，如果把它在一點 $x$ 上無限放大，最終會近似成為平面，這個平面就是 $x+T_f(x)$ 。（如果你不明白這段在說什麼，請拖到最下方看注1。）下圖是一個例子：

從而，在曲面 $f(x)=0$ 上一點 $x$ 周圍，我們把空間分成了三部分：

$N_f^+cup N_f^-cup T_f=R^n$

下面來看看等式約束和不等式約束的可行方向，也就是這樣一些方向，朝它們移動一點，約束依然近似滿足。

1 如果點 $x^*$ 滿足等式約束 $h(x^*)=0$ ，那麼在切平面方向 $T_{h}$ 上滑動，這個等式約束依然近似滿足，所以可行方向為 $T_{h}$ 。

2 如果點 $x^*$ 滿足不等式約束 $g(x^*)<0$ ，說明它在曲面 $g(x)=0$ 的某一側，並且不在邊界上，所以無論朝哪個方向跑，它仍然滿足約束 $g(x)leq0$ ，可行方向為 $R^n$ 。

3 如果點 $x^*$ 滿足 $g(x^*)=0$ ，因為約束條件是 $g(x)leq0$ ， $x^*$ 可以朝切平面 $T_{g}$ 中的方向滑動，保持在 $g(x)=0$ 上，也可以往 $g$ 的負梯度方向 $N_{g}^-$ 跑，讓 $g$ 值減小，不等式約束依然成立。但是不能往正梯度方向跑，因為會造成 $g(x)>0$ ，違背不等式約束。所以可行方向是 $N_{g}^-cup T_{g}$ ，這是n維空間的一半，或者n-1維子空間與一條垂直於它的射線的並。

三種情況我們總結在下表中：

總結一下就是：假設一個點滿足某約束，可行方向是這樣一些方向，在這些方向上移動一點點，點仍然近似滿足約束。對等式約束，可行方向是切空間；對不等式約束，如果點正好在邊界上，可行方向是半空間，如果不在邊界上，可行方向是全空間。

四、多約束的可行方向

上面我們討論了一個約束的情況，假如有兩個約束或者多個約束，那麼這些約束的交集就是更低維的「曲面」。比如在三維空間中，兩張曲面的交集是一維曲線。對於這些「交集」上的點，或者同時滿足多個約束的點，我們仍然可以討論它的可行方向：讓這些點朝可行方向移動，能夠近似滿足所有條件。仔細琢磨不難發現：

滿足多個約束的點的可行方向是每個約束的可行方向的交集。

為了便於理解，我們舉兩個例子：

例1：兩個等式約束 $h_i(x)=0$ 和 $h_j(x)=0$ 是三維空間中的二維曲面，二者的交是一維曲線（下圖中藍白相間的部分），考慮曲線上的一個點 $x$ ，這一點作為曲線上的一點，切空間是一維的，也就是曲線的切線，而這條切線恰好是兩個等式約束的切平面的交。

例2：等式約束 $h_j(x)=0$ 是下圖右邊的球面，不等式約束 $g_ileq0$ 是左邊綠色球面外面的空間區域，同時滿足二者的可行域是右邊球面露在左邊球面外面的部分（紅白相間的部分）。為保持兩個約束仍然滿足，點 $x$ 既可以在兩球面交線上滑動 $(h_j(x)=g_i(x)=0)$ ，也可以朝右邊球面上移動 $(h_j(x)=0,g_i(x)<0)$ ，所以可行方向是下圖右邊那半塊玻璃。同時，可行方向也是 $h_j(x)=0$ 的可行方向、平面 $T_{h_j}$ （下圖中右邊那塊平面玻璃）和 $g_ileq0$ 在邊界上的可行方向、半空間 $T_{g_i}cup N_{g_i}^-$ （下圖中左面那塊平面玻璃靠上的所有區域）的交集。

五、KKT條件的證明

我們在第二小節中說過，KKT條件等價於在極值點 $x^*$ ，目標函數增大的方向不能在可行方向 $F(x^*)$ 中，可行方向是指 $x^*$ 朝它移動一點點，仍然滿足約束條件的方向。

目標函數增大的方向是 $N_f^+(x^*)={lambda abla f(x^*),lambdageq0}$ ，這就意味著

$N_f^+(x^*) ot F(x^*)$ 或者 $abla f(x^*) ot F(x^*)$

就是說， $abla f(x^*)$ 在 $F(x^*)$ 中不能有分量，或者說投影是0，這個式子等價於：

$abla f(x^*) subset R^n-F(x^*)$

我們下面把所有約束分為三部分：

1 等式約束 $h_j(x^*)=0$ ，可行方向是 $T_{h_j}$ ;

2 不等式約束， $g_i(x^*)leq 0$ ， $x^*$ 在邊界上， $g_i(x^*)=0$ ，可行方向是 $T_{g_i}cup N_{g_i}^-$ ;

3 不等式約束， $g_k(x^*)leq 0$ ， $x^*$ 不在邊界上， $g_k(x^*)<0$ ，可行方向是 $R^n$ 。

那麼同時滿足所有有約束的點的可行方向就是所有這些可行方向的交集：

$F(x^*)=left( cap_jT_{h_j} ight)capleft( cap_i (T_{g_i} cup N_{g_i}^-) ight)capleft( cap_k R^n ight)$

第三部分直接消失了，從而在KKT表達等式中不會出現不在邊界上的不等式約束。再利用集合的德摩根公式可得：

$R^n-F(x^*)=left( cup_j(R^n-T_{h_j}) ight)cupleft( cup_i (R^n-T_{g_i} cup N_{g_i}^-) ight)$

整理一下，得：

$abla f(x^*) subset R^n-F(x^*)=left( cup_j N_{h_j} ight)cupleft( cup_i N_{g_i}^+ ight)$

這就是KKT條件。

注1：方向的線性結構

在上面的論述中我們使用了定義在方向上的線性結構，這裡詳細解釋一下。

大家都知道曲線和曲面生活在歐幾里德空間。歐式空間是這樣一種空間，其上定義了內積運算，從而可以測量長度、角度，並且這些幾何量與人們的日常直覺吻合。笛卡爾建立了直角坐標系，從而我們可以在歐式空間上建立線性結構，讓它等價（同構）於 $R^n$ 。

「方向」這個術語並不單獨存在，它依附於一個點，從一個點出發的方向才有意義。因為在我們的問題中這個點固定在某個極值點 $x^*$ ，起始點可以被省略，我們直接說某個方向。所有這些方向又構成了一個線性空間 $R^n$ ，這就好像如果你把坐標原點移到 $x^*$ ，那麼從 $x^*$ 出發的一個向量 $v$ 可以帶我們去 $R^n$ 的任意一處。

假設有兩個（從 $x^*$ 出發的）方向的集合 $A$ 和 $B$ ，我們可以定義它們的並集是 ${u+v,uin A,vin B}$ ，舉一個簡單的例子，假設在 $R^3$ 中， $A$ 是與x軸平行的所有方向，那麼

$A={(alpha, 0, 0)|alphain R}$ ，

是三維線性空間的一個一維子空間。 $B$ 是yz平面上的所有方向，那麼

$B={(0, eta, gamma)|eta,gammain R}$ ，是一個二維子空間。因為二者的並集是全空間：

$Acup B={(alpha, eta, gamma)|alpha,eta,gammain R}=R^3$

又因為二者交集只有0元素，

$A cap B = {(0,0,0)}$ 或者 $Aot B$ ，

我們說二者互為補集或者

$B=R^3-A$ 。

推廣一下就是說，如果一維直線 $A$ 不在n-1維平面 $B$

上，那麼它們的並集是全空間，但是二者不一定互為補集。當一維子空間恰好由n-1維平面的法線方向張成時，二者互補。

在一個nonlinear program中，要想取到optimum，一定要滿足Fritz John Condition（通過Gordon" Theorem得到）。而通過添加一些constraint qualification，可以推導出一旦滿足Kuhn Tucker Condition則一定取到optimum。KKT語言描述就是objective function的gradient是所有constraint的gradient的線性組合。

除了對偶鬆弛

別的條件和拉格朗日橙子法一摸一樣吧OAO

對偶問題很多時候可以看作原問題的擾動

對偶問題的弱對偶性可以由兩個不等式得出來，一個是加非正項，一個是取下界

如果滿足強對偶性，因為最終的解相等，那麼兩個不等式必須取等號，即非正項必須為0，下界必須取到，由問題的凸性，可以知道條件是梯度為0。

KKT是一共有4個條件，前兩個是問題和對偶問題本身的條件，再加上上面說的兩個條件，就構成了KKT。

幾何上去理解，目標函數的負梯度位於可行域在最優點處的法錐之中。

像一個坑，往哪都爬不出去…

What is an intuitive explanation of the KKT conditions? 這裡講的很好；上面那位同學說的約束條件的梯度的線性組合和這個圖搭配起來看就ok了