拉格朗日乘子法和 KKT 條件

????這篇博文中直觀上講解了拉格朗日乘子法和 KKT 條件，對偶問題等內(nèi)容钥星。
????首先從無約束的優(yōu)化問題講起沾瓦，一般就是要使一個表達式取到最小值：
$min \quad f(x)$
????如果問題是 $max \quad f(x)$ 也可以通過取反轉(zhuǎn)化為求最小值 $min \quad-f(x)$ ，這個是一個習(xí)慣。對于這類問題在高中就學(xué)過怎么做贯莺。只要對它的每一個變量求導(dǎo)风喇，然后讓偏導(dǎo)為零，解方程組就行了乖篷。

image.png

????所以在極值點處一定滿足 $\frac {df(x)}{dx}=0$ （只是必要條件响驴，比如 $f(x)=x^3$ 在 $x=0$ 處就不是極值點），然后對它進行求解撕蔼，再代入驗證是否真的是極值點就行了豁鲤。對于有些問題可以直接通過這種方法求出解析解（如最小二乘法）。
????但是也有很多問題解不出來或者很難解鲸沮，所以就需要梯度下降法琳骡、牛頓法、坐標(biāo)下降法之類的數(shù)值迭代算法了（感知機讼溺、logistic 回歸中用到）楣号。
????對于這些迭代算法就像下面這張圖一樣，我們希望找到其中的最小值怒坯。一個比較直觀的想法是先找一個起點炫狱，然后不斷向最低點靠近。就先把一個小球放到一個碗里一樣剔猿。

image.png

????一開始要找一個起始點视译，然后確定走的方向和距離，最后還要知道什么時候停止归敬。這三步中最難的應(yīng)該是確定走的方向酷含。走的慢點還可以接受，要是方向錯了就找不到最小值了~汪茧。所以走的距離可以簡單的設(shè)為一個比較小的值椅亚。起始點可以隨機選一個 $(x_0,y_0)$ 。關(guān)鍵是方向舱污，可以選擇 $(x_0,y_0)$ 處的梯度的反方向呀舔，這是函數(shù)在這個點下降最快的方向（原因可以看知乎中憶臻的回答）。它是一個向量扩灯，然后它的大小就是走的距離别威，為了防止太大而走過頭，導(dǎo)致不斷在最小值附近震蕩驴剔，需要乘上一個比較小的值（稱為學(xué)習(xí)率），最終的停止條件就是梯度的大小很接近于 0（在極值點處的梯度大小就是 0）就行了粥庄。這種方法依靠梯度確定下降方向的方法叫做梯度下降法丧失。
對 $f(x)$ 求極小值的流程就是：

隨機選定 $x_0$
得到函數(shù)在 $x_0$ 的梯度，然后從 $x_0$ 向前走一步惜互。計算式是： $x_0^{new}=x_0^{old} - \alpha\nabla f(x)$
重復(fù)第 2 步布讹，直到梯度接近于 0（小于一個事先設(shè)定的很小的數(shù)）琳拭，或者到達指定的迭代上限。

image.png

????除了這種方法之外描验，其中第 2 步還可以這樣做白嘁，固定 $x$ , 把它作為常數(shù)。就變成只有一個變量的優(yōu)化問題了膘流，直接求導(dǎo)為 0 就可以得到最優(yōu)點絮缅，向前走到 $(x_0, y_1)$ 處，然后固定 $y_1$ , 對 $x$ 進行相同的操作呼股。這種每次只優(yōu)化一個變量的方法叫做坐標(biāo)下降法耕魄。

image.png

????然后就是進一步的，我們可能要在滿足一定約束條件的情況下最小化目標(biāo)函數(shù)彭谁，比如有一個等式約束：
$\begin{align*} min \quad f(x)\\ & s.t. \quad h(x) = 0 \end{align*}$
????解決這個的時候問題不能先用上面的方法求出 $f(x)$ 的極值點吸奴，然后留下滿足方程 $h(x)=0$ 的。因為這個問題的解可能根本不是 $min \quad f(x)$ 的解缠局，它們是沒有關(guān)系的则奥。那么還是要從問題本身去找線索：

image.png

????如圖，其中的圓圈是指目標(biāo)函數(shù) $f(x狭园，y)$ 投影在平面上的等值線读处，表示在同一個圓圈上，黑線是約束條件 $h(x)=0$ 的函數(shù)圖像妙啃。所以等值線與函數(shù)圖像相交的點其實就是所有滿足約束的點档泽。那么極值點只有可能在等值線與函數(shù)圖像相切的地方取到，因為如果在相交的地方取到揖赴，那么沿著 $h(x)$ 的圖像往前走或者往后走馆匿，一定還有其它的等值線與它相交，也就是 $f(x,y)$ 的值還能變大和變小燥滑，所以交點不是極值點渐北，只有相切的時候才有可能是極值點(不可能同時變大和變小了)。在相切的地方 $h(x)$ 的梯度和 $f(x,y)$ 的梯度應(yīng)該是在同一條直線上的铭拧。（這一點可以這么想赃蛛，在切點處兩個函數(shù)的梯度都與切平面垂直，所以在一條直線上）
????所以滿足條件的極值點一定滿足： $\nabla f(x,y)=\lambda \nabla h(x,y)$ ( $\lambda = 0$ 是允許的搀菩，表示 f(x,y) 本身的極值點剛好在切點上)呕臂，然后和原來的等式方程 $h(x,y)=0$ 聯(lián)立，然后只要解出這個方程組肪跋，就可以得到問題的解析解了歧蒋。當(dāng)然也存在解不出來的情況，就需要用罰函數(shù)法之類的方法求數(shù)值解了。
????為了方便和好記谜洽，就把原來的優(yōu)化問題寫成 $f(x,y) + \lambda h(x,y)$ 的形式萝映，然后分別對 $\lambda,x,y$ 求偏導(dǎo)，并且令偏導(dǎo)為 $0$ 就行了阐虚，和之前得到的方程組是一樣的序臂。這種方法叫拉格朗日乘數(shù)法。
????如果有多個等式約束怎么辦呢实束，如下圖：

image.png

????這里的平面和球面分別代表了兩個約束 $h_1(x)$ 和 $h_2(x)$ 奥秆，那么這個問題的可行域就是它們相交的那個圓。這里藍色箭頭表示平面的梯度磕洪，黑色箭頭表示球面的梯度吭练，那么相交的圓的梯度就是它們的線性組合（只是直觀上的~），所以在極值點的地方目標(biāo)函數(shù)的梯度和約束的梯度的線性組合在一條直線上析显。所以就滿足：
$\nabla f(x) = \lambda \sum_{i=1}^{2}\mu_{i}\nabla h_i(x)=\sum_{i=1}^{2}\lambda_{i}\nabla h_i(x)\\ h_1(x)=0\\ h_2(x)=0$
????大于2個約束的情況也一樣鲫咽。為了好記，將原來的約束的問題寫成 $L(x,\lambda)=f(x)+\sum_{i-1}^{n}\lambda_{i}\nabla h_{i}(x)$ 的形式谷异，然后對 $x$ 分尸、 $\lambda$ 求偏導(dǎo)，然后讓它們?yōu)?0歹嘹。結(jié)果像上面一樣直接列方程組是一樣的箩绍。這個可以看做是一種簡記，或者是對偶問題尺上，這個函數(shù)叫做拉格朗日函數(shù)材蛛。
????再進一步，如果問題中既有等式約束怎抛，又有不等式約束怎么辦呢卑吭？對于：
$\begin{align*} min \quad f(x)\\ & s.t. \quad h(x) = 0\\ &\quad \quad \quad g(x) \leq 0 \end{align*}$
????當(dāng)然也同樣約定不等式是 $\leq$ ，如果是 $\geq$ 只要取反就行了马绝。對于這個問題先不看等式約束豆赏，對于不等式約束和目標(biāo)函數(shù)的圖：

image.png

????陰影部分就是可行域，也就是說可行域從原來的一條線變成了一塊區(qū)域富稻。那么能取到極值點的地方可能有兩種情況：

還是在 $h(x)$ 和等值線相切的地方
$f(x)$ 的極值點本身就在可行域里面掷邦。

????因為如果不是相切，那么同樣的椭赋，對任意一個在可行域中的點抚岗，如果在它附近往里走或者往外走， $f(x)$ 一般都會變大或者變小哪怔，所以絕大部分點都不會是極值點宣蔚。除非這個點剛好在交界處廷痘，且和等值線相切；或者這個點在可行域內(nèi)部件已，但是本身就是 $f(x)$ 的極值點。如下圖（維基百科上的圖~）：

image.png

????對于第一種情況元暴，不等式約束就變成等式約束了篷扩，對 $f(x) + \lambda h(x) + \mu g(x)$ 用拉格朗日乘子法：
$\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\ h(x)=0\\ g(x)=0\\ \mu \geq 0$
????這里需要解釋一下，為什么不是 $\mu \neq0$ 而是 $\mu \geq 0$ 茉盏。后面的約束比前面的更強鉴未。看“不等式約束”那個圖鸠姨，我們已經(jīng)知道了問題中的可行域是在 $g(x)\leq0$ 一側(cè)铜秆，而 $g(x)$ 的梯度是指向大于 0 的一側(cè)，也就是不是可行域的一側(cè)讶迁。而求的問題是極小值连茧，所以 $f(x)$ 在交點處的梯度是指向可行域的一側(cè)，也就是說兩個梯度一定是相反的巍糯。所以也就可以確定這里的系數(shù)一定是大于 0 的啸驯。而等式約束由于不知道 $h(x)$ 的梯度方向，所以對它沒有約束祟峦，那么為什么 $\mu$ 還能等于 0 呢罚斗，因為極值點可能剛好在 $g(x)$ 上。
????對于第二種情況宅楞，不等式約束就相當(dāng)于沒有针姿，對 $f(x) + \lambda h(x)$ 用拉格朗日乘子法：
$\nabla f(x)+\lambda \nabla h(x)= 0\\ h(x)=0\\ g(x) \leq 0$
????最好把兩種情況用同一組方程表示出來。對比一下兩個問題厌衙，不同的是第一種情況中有 $\mu \geq 0$ 且 $g(x)=0$ , 第二種情況 $\mu = 0$ 且 $g(x) \leq 0$ 距淫。綜合兩種情況，可以寫成 $\mu g(x) = 0$ 且 $\mu \geq 0$ 且 $g(x) \leq 0$ ：
$\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\ \mu g(x) = 0\\ \mu \geq 0 \\ h(x)=0\\ g(x) \leq 0$
????這個就是 KKT 條件迅箩。它的含義是這個優(yōu)化問題的極值點一定滿足這組方程組溉愁。（不是極值點也可能會滿足，但是不會存在某個極值點不滿足的情況）它也是原來的優(yōu)化問題取得極值的必要條件饲趋，解出來了極值點之后還是要代入驗證的拐揭。但是因為約束比較多，情況比較復(fù)雜奕塑，KKT 條件并不是對于任何情況都是滿足的堂污。要滿足 KKT 條件需要有一些規(guī)范性條件（Regularity conditions），就是要求約束條件的質(zhì)量不能太差龄砰，常見的比如：

LCQ：如果 $h(x)$ 和 $g(x)$ 都是形如 $Ax+b$ 的仿射函數(shù)盟猖，那么極值一定滿足 KKT 條件讨衣。
LICQ：起作用的 $g(x)$ 函數(shù)（即 $g(x)$ 相當(dāng)于等式約束的情況）和 $h(x)$ 函數(shù)在極值點處的梯度要線性無關(guān)，那么極值一定滿足 KKT 條件式镐。
Slater 條件：如果優(yōu)化問題是個凸優(yōu)化問題反镇，且至少存在一個點滿足 $h(x) = 0$ 和 $g(x) = 0$ ，極值一定滿足 KKT 條件娘汞。并且滿足強對偶性質(zhì)（下面會講）歹茶。

???? 這里的 Slater 條件比較重要，因為它可以推導(dǎo)出強對偶性質(zhì)（下面會講到你弦，它比 KKT 條件還好）惊豺。它需要原問題是凸優(yōu)化問題。所謂凸優(yōu)化就是這個優(yōu)化問題的優(yōu)化函數(shù)是凸函數(shù)禽作，并且可行域是凸集尸昧。可行域數(shù)凸集就要求其中的 $h(x)\leq0$ 的條件中 $h(x)$ 必須也是凸函數(shù)旷偿，而 $g(x) \leq0$ 中的 $g(x)$ 必須是 $Ax+b$ 形式的烹俗，也就是仿射函數(shù)（比如二維的情況，可行域就在 $g(x)$ 這條曲線上狸捅，那么 $g(x)$ 必須得是直線才能滿足凸集的定義）衷蜓。
???? 其它條件還有很多，可以看維基百科尘喝。
????如果有多組等式約束 $g_i(x) =0 \quad (i=1,..,n)$ , 和不等式約束 $h_i(x) \neq0 \quad (i=1,..,n)$ 也是一樣磁浇，只要做個線性組合就行了：
$\nabla f(x)+\sum_{i=1}^{n}\lambda_i \nabla h_i(x)+\sum_{i=1}^{n}\mu_i \nabla g_i(x) = 0\\ \mu_i g(x)_i = 0\\ \mu_i \geq 0\\ h_i(x)=0\\ g_i(x) \leq 0\\ i = 1,2,...,n$
????問題到這里就大致解決了，KKT 條件雖然從理論上給出了極值的必要條件朽褪，但是一般實際解的時候直接方程也是很困難的（特別是約束很多的時候）置吓，一般也會采用罰函數(shù)法等數(shù)值方法。
????為了更好的解決這個優(yōu)化問題缔赠，數(shù)學(xué)家還找到了它的對偶問題衍锚。找一個優(yōu)化問題的對偶問題的一般因為是對偶問題比原問題更好解決，并且對偶問題的解和原問題是一樣的嗤堰。上面的拉格朗日函數(shù)也可以看做原問題的對偶問題戴质。
????為了去掉問題中的約束，可以把它們作為懲罰項加到目標(biāo)函數(shù)中 $min_{x}f(x) + M h(x) + N g(x)$ 其中 M, N 是兩個很大的正數(shù)踢匣，在數(shù)值解法中可以直接這樣做告匠，這個就是罰函數(shù)法的思路。不過在理論推導(dǎo)時這樣做是不嚴(yán)謹(jǐn)?shù)睦牖＃?M, N 為無窮大后专。所以就把原問題改寫 $L(x,\mu,\lambda) = min_{x}max_{\mu,\lambda}f(x) + \lambda h(x) + \mu g(x)$ 。這個式子可以這么理解输莺，現(xiàn)在外層給定任意一個 $x_{0}$ 值戚哎，然后內(nèi)層在給定的 $x_{0}$ 下優(yōu)化那個函數(shù)裸诽，讓它最小。然后外層選能夠讓內(nèi)層得到的值最大的一個 $x_{0}$ 型凳，得到的函數(shù)表達式就是：
$L(x,\mu,\lambda)= \left\{\begin{matrix} f(x) & (x \quad滿足約束)\\ \infty & (x \quad不滿足約束)\\ \end{matrix}\right.$
所以外層選的那個 $x_{0}$ 一定滿足約束丈冬，否則，內(nèi)層的 max 的時候會讓 $\mu$ 或者 $\lambda$ 為無窮大甘畅。外層不會選那些能讓內(nèi)層得到無窮大的 $x$ 值殷蛇。這樣改寫就和原來的帶約束形式完全一致了，但是形式不同橄浓。這樣可以利用 $max \quad min f(x) \leq min \quad max(f(x))$ 這個公式（這個很好理解， $min f(x) \leq min\quad max f(x)$ , 然后就有這個公式了）亮航，得到原問題的最小值的一個下界荸实，就是:
$min_{x}max_{\mu,\lambda}f(x) + \lambda h(x) + \mu g(x) \geq max_{\mu,\lambda}min_{x}f(x) + \lambda h(x) + \mu g(x)$
????前面的就是原函數(shù)，后面的是它的一個下界缴淋。那么為什么要這樣做呢? 是因為后面的一定是一個凸規(guī)劃(理論上證明了的)准给，比較好解決。但是這個只是一個下界重抖，它們之間還是有一定的差距露氮。這個差距叫對偶誤差（duality gap）。對偶誤差如果為 0 其實是一個非常好的性質(zhì)钟沛，表示可以直接求解后面的問題得到原問題的解畔规，這種性質(zhì)叫強對偶性質(zhì)，否則就只是弱對偶恨统。
????強對偶性質(zhì)非常好叁扫，但是要求也很苛刻，比 KKT 條件要苛刻畜埋。如果問題滿足強對偶一定也滿足 KKT 條件莫绣，反之不一定。對于這類優(yōu)化問題悠鞍，KKT 條件对室、強對偶、規(guī)范性條件之間的關(guān)系是：