深入理解拉格朗日乘子法 和KKT條件

1、【整理】深入理解拉格朗日乘子法(Lagrange Multiplier)和KKT條件在求解最優(yōu)化問題中，拉格朗日乘子法(Lagrange Multiplier)和 KKT( Karush Kuhn Tucker)條件是兩種最常 用的方法。在有等式約束時(shí)使用拉格朗日乘子法，在有不等 約束時(shí)使用KKT條件。 我們這里提到的最優(yōu)化問題通常 是指對(duì)于給定的某一函數(shù)，求其在指定作用域上的全局最小 值(因?yàn)樽钚≈蹬c最大值可以很容易轉(zhuǎn)化，即最大值問題可以 轉(zhuǎn)化成最小值問題)。提到KKT條件一般會(huì)附帶的提一下拉 格朗日乘子。對(duì)學(xué)過高等數(shù)學(xué)的人來說比較拉格朗日乘子應(yīng) 該會(huì)有些印象。二者均是求解最優(yōu)化問題的方法，

2、不同之處 在于應(yīng)用的情形不同。一般情況下，最優(yōu)化問題會(huì)碰到一下三種情況：(1)無約束條件 這是最簡單的情況， 解決方法通常是函數(shù)對(duì)變量求導(dǎo)，令求導(dǎo)函數(shù)等于0的點(diǎn)可 能是極值點(diǎn)。將結(jié)果帶回原函數(shù)進(jìn)行驗(yàn)證即可。(2)等式約 束條件設(shè)目標(biāo)函數(shù)為f(x)，約束條件為h_k(x)，形如:s.t.表示subject to，受限于”的意思，l表示有l(wèi)個(gè)約束條 件。則解決方法是消元法或者拉格朗日法。消元法比較簡單不在贅述，這里主要講拉格朗日法， 因?yàn)楹竺嫣岬降腒KT條件是對(duì)拉格朗日乘子法的一種泛化。 例如給定橢球：求這個(gè)橢球的內(nèi)接長方體的最大體積。這個(gè)問題實(shí)際上就是條件極值 問題，即在條件下，求的最大值。當(dāng)然

3、這個(gè)問題實(shí)際可以先根據(jù)條件消去z (消元法)，然后帶入轉(zhuǎn)化為無 條件極值問題來處理。但是有時(shí)候這樣做很困難，甚至是做 不到的，這時(shí)候就需要用拉格朗日乘數(shù)法了。首先定義拉格朗日函數(shù)F(x):(其中入k是各個(gè)約束條件的待定系數(shù)。)然后解變量的偏導(dǎo)方程：, 如果有l(wèi)個(gè)約束條件，就應(yīng)該有1+1個(gè)方程。求出的方程組的解就可 能是最優(yōu)化值(高等數(shù)學(xué)中提到的極值)，將結(jié)果帶回原方 程驗(yàn)證就可得到解。回到上面的題目，通過拉格朗日乘數(shù)法將問題轉(zhuǎn)化為對(duì)求偏導(dǎo)得到聯(lián)立前面三個(gè)方程得到和，帶入第四個(gè)方程解之 帶入解得最大體積為：至于為什么這么做可以求解最優(yōu)化？維基百科上給出了一個(gè)比較好的 直觀解釋。舉個(gè)二維最優(yōu)化的例

4、子：min f(x,y)s.t. g(x,y) = c 這里畫出z=f(x,y)的等高線(函數(shù)登高線定義見百度百科)： 綠線標(biāo)出的是約束g(x,y)=c的點(diǎn)的軌跡。藍(lán)線是f(x,y)的等 高線。箭頭表示斜率，和等高線的法線平行。從梯度的方向 上來看，顯然有d1d2。綠色的線是約束，也就是說，只要 正好落在這條綠線上的點(diǎn)才可能是滿足要求的點(diǎn)。如果沒有 這條約束,f(x,y)的最小值應(yīng)該會(huì)落在最小那圈等高線內(nèi)部的 某一點(diǎn)上。而現(xiàn)在加上了約束，最小值點(diǎn)應(yīng)該在哪里呢？顯 然應(yīng)該是在f(x,y)的等高線正好和約束線相切的位置，因?yàn)?如果只是相交意味著肯定還存在其它的等高線在該條等高 線的內(nèi)部或者外部，使

5、得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值 更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切的時(shí)候, 可能取得最優(yōu)值。 如果我們對(duì)約束也求梯度?g(x,y)，則 其梯度如圖中綠色箭頭所示。很容易看出來，要想讓目標(biāo)函 數(shù)f(x,y)的等高線和約束相切，則他們切點(diǎn)的梯度一定在一 條直線上(f和g的斜率平行)。也即在最優(yōu)化解的時(shí)候：？f(x,y)=A(?g(x,y)-C)(其中？為梯度算子；即：f(x)的梯度=A* g(x)的梯度，入是常數(shù)， 可以是任何非0實(shí)數(shù)，表示左右兩邊同向。) 即： f(x,y)+A(g(x,y)?c)=0A知那么拉格朗日函數(shù)：F(x,y)=f(x,y)+A(g(x,y)?c)在達(dá)到極值

6、時(shí)與f(x,y)相等，因?yàn)?F(x,y)達(dá)到極值時(shí)g(x,y)?c總等于零。min( F(x,A)取得極小值時(shí)其導(dǎo)數(shù)為0，即vf(x)+vXni=Aihi(x)=0,也就是說f(x) 和h(x)的梯度共線。簡單的說，在F(x,A)取得最優(yōu)化解的時(shí)候即 F(x,A)取極值(導(dǎo)數(shù)為 0 ,vf(x,y)+A(g(x,y)?c)=0) 的時(shí)候,f(x)與g(x)梯度共線,此時(shí)就是在條件約束g(x)下， f(x)的最優(yōu)化解。(3 )不等式約束條件 設(shè)目標(biāo)函數(shù) f(x)，不等式約束為g(x)，有的教程還會(huì)添加上等式約束條件h(x)。此時(shí)的約束優(yōu)化問題描述如下：則我們定義不等式約束下的拉格朗日函數(shù)L ,則L表達(dá)式為： 其中f(x)是原目標(biāo)函數(shù)，hj(x)是第j個(gè)等式約束條件，入j是對(duì) 應(yīng)的約束系數(shù),gk是不等式約束，uk是對(duì)應(yīng)的約束系數(shù)。 常用的方法是KKT條件，同樣地，把所有的不等式約束、等 式約束和目標(biāo)函數(shù)全部寫為一個(gè)式子L(a, b, x)= f(x) + a*g(x)+b*h(x) ,KKT條件是說最優(yōu)值必須滿足以下條件:1 )L(a, b, x)對(duì) x 求導(dǎo)為零； 2 )h(x) =0;3 )a*g(x) = 0;求取這些等式之后就能得到候選最優(yōu)值。其中第三個(gè)式子非常有趣，因?yàn)間(x)接下