拉格朗日乘子法和KKT條件
- 2019 年 11 月 5 日
- 筆記
求解最優化問題中，拉格朗日乘子法和KKT條件是兩種最常用的方法。在有等式約束時使用拉格朗日乘子法，在有不等式約束時使用KKT條件。這個最優化問題指某一函數在作用域上的全局最小值（最小值與最大值可以相互轉換）。
最優化問題通常有三種情況(這裡說兩種)：
1. 無約束條件
求解辦法是求導等於0得到極值點。將結果帶回原函數驗證。
2、等式約束條件
設目標函數f(x)，約束條件hk(x)，
min f(x) s.t. hk(x)=0 (k = 1,2…l)
l表示有l個約束條件。
該類問題解決辦法是消元法或拉格朗日法。消元法簡單，這裡講拉格朗日法，後面提到的KKT條件是對拉格朗日乘子法的泛化。
例子：
橢球
內接長方體的最大體積，即求 f(x,y,z) = 8xyz 的最大值。
方法1：消元法
根據條件消去z，然後帶入函數轉化為無條件極值問題。（有時這種方法麻煩，甚至解不出來）
方法2：拉格朗日乘法
思想：通過引入拉格朗日乘子將含有n個變數和k個約束條件的約束優化問題轉化為含有(n+k)個變數的無約束優化問題。
首先定義拉格朗日函數F(x)，f(x)為目標函數，h(x)為約束條件：
（λk是各個約束條件的待定係數）
對各個變數求偏導：
方程組的解就可能是最優化值，將結果帶回原方程驗證。
上面的函數，通過拉格朗日乘數法將問題轉化為：
對 F(x,y,z,λ) 求偏導得到
聯立前面3個方程得到 bx = ay 和 az = cx，帶入第4個方程：
帶入原函數得到最大體積：
為什麼這麼做是最優解？
舉個例子：min f(x,y) s.t. g(x,y) = c
畫出 z = f(x,y)的等高線
綠線是約束g(x,y) = c的軌跡。藍線是f(x,y)的等高線。箭頭表示斜率，和等高線的發現平行。從梯度的方向看，d1>d2(梯度下降法越接近目標，步長越小，前進越慢)。
在沒有約束條件，f(x,y)的最小值是落在最裡面等高線內部的某一點。加上約束條件的 f(x,y) 最小值是 f(x,y)的等高線和約束線相切的位置，因為如果只是相交意味著還存在其它的等高線在該等高線的內部或外部，使新的等高線與目標函數的交點值更大或更小，只有等高線與目標函數的曲線相切時，取到最優值。
從圖看出，想讓目標函數 f(x,y) 的等高線和約束 g(x,y) 相切，則他們切點的梯度在一條直線上( f 和 g 斜率平行)。
即在最優解的時候：∇f(x,y)=λ（∇g(x,y)-C) （∇為梯度運算元，即：f(x)的梯度 = λ*g(x)的梯度，λ是非0常數）
即：▽[f(x,y)+λ(g(x,y)−c)]=0 (λ≠0)
那麼拉格朗日函數： F(x,y)=f(x,y)+λ(g(x,y)−c) 在達到極值時與 f(x,y) 相等，因為 F(x,y) 達到極值時 g(x,y)-c 總等於0。
min(F(x,λ))取得極小值時其導數為0，即f(x)和h(x)的梯度共線。
簡單的說，在F(x,λ)取最優解的時候，即F(x,λ)取極值的時候(導數為0，▽[f(x,y)+λ(g(x,y)−c)]=0)。f(x)與g(x)梯度共線，此時就是在條件約束g(x)下，f(x)的最優解。
3、不等式約束
設目標函數f(x)，不等式約束為g(x)，等式約束條件h(x)。此時的約束優化問題描述如下：
我們定義不等式約束下的拉格朗日函數L：
其中f(x)是目標函數，
是第j個等式約束條件，
是對應的約束係數，
是第k個不等式約束，
是對應的約束係數。
不等式約束常用的方法是KKT條件，同樣的，把所有的不等式約束、等式約束和目標函數全部寫為一個式子L(a, b, x)= f(x) + a*g(x)+b*h(x)
KKT條件是說最優值必須滿足以下條件：
- L(a, b, x)對x求導為零；
- h(x) =0;
- a*g(x) = 0;
求取這些等式之後就能得到候選最優值。其中第三個式子，因為g(x)<=0，如果要滿足這個等式，必須a=0或者g(x)=0。 這是SVM的很多重要性質的來源，如支援向量的概念。
