在求解最優(yōu)化問(wèn)題中顶伞，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法。在有等式約束時(shí)使用拉格朗日乘子法，在有不等約束時(shí)使用KKT條件。
我們這里提到的最優(yōu)化問(wèn)題通常是指對(duì)于給定的某一函數(shù)，求其在指定作用域上的全局最小值(因?yàn)樽钚≈蹬c最大值可以很容易轉(zhuǎn)化漠另，即最大值問(wèn)題可以轉(zhuǎn)化成最小值問(wèn)題)。提到KKT條件一般會(huì)附帶的提一下拉格朗日乘子跃赚。對(duì)學(xué)過(guò)高等數(shù)學(xué)的人來(lái)說(shuō)比較拉格朗日乘子應(yīng)該會(huì)有些印象笆搓。二者均是求解最優(yōu)化問(wèn)題的方法，不同之處在于應(yīng)用的情形不同纬傲。 一般情況下满败，最優(yōu)化問(wèn)題會(huì)碰到一下三種情況。
無(wú)約束條件
這是最簡(jiǎn)單的情況叹括，解決方法通常是函數(shù)對(duì)變量求導(dǎo)算墨，令求導(dǎo)函數(shù)等于0的點(diǎn)可能是極值點(diǎn)。將結(jié)果帶回原函數(shù)進(jìn)行驗(yàn)證即可汁雷。等式約束條件
設(shè)目標(biāo)函數(shù)為f(x)净嘀，約束條件為h_k(x)，形如:
s.t. 表示subject to 侠讯，“受限于”的意思挖藏，l表示有l(wèi)個(gè)約束條件。
則解決方法是消元法或者拉格朗日法厢漩。消元法比較簡(jiǎn)單不在贅述膜眠，這里主要講拉格朗日法，因?yàn)楹竺嫣岬降腒KT條件是對(duì)拉格朗日乘子法的一種泛化。例如給定橢球:
求這個(gè)橢球的內(nèi)接長(zhǎng)方體的最大體積宵膨。這個(gè)問(wèn)題實(shí)際上就是條件極值問(wèn)題架谎，即在條件
下，求
的最大值辟躏。當(dāng)然這個(gè)問(wèn)題實(shí)際可以先根據(jù)條件消去 z (消元法)谷扣，然后帶入轉(zhuǎn)化為無(wú)條件極值問(wèn)題來(lái)處理。但是有時(shí)候這樣做很困難捎琐，甚至是做不到的抑钟，這時(shí)候就需要用拉格朗日乘數(shù)法了。 首先定義拉格朗日函數(shù)F(x)：
對(duì)
求偏導(dǎo)則
聯(lián)立前面三個(gè)方程得到 bx = ay 和 az = cx, 帶入第四個(gè)方程解之
帶入解得最大體積為：
至于為什么這么做可以求解最優(yōu)化拨黔？維基百科上給出了一個(gè)比較好的直觀解釋。
舉個(gè)二維最優(yōu)化的例子：
min f(x,y)
s.t. g(x,y) = c
這里畫(huà)出z=f(x,y)的等高線（函數(shù)登高線定義見(jiàn)百度百科）：
綠線標(biāo)出的是約束g(x,y)=c的點(diǎn)的軌跡绰沥。藍(lán)線是f(x,y)的等高線篱蝇。箭頭表示斜率，和等高線的法線平行徽曲。從梯度的方向上來(lái)看零截，顯然有d1>d2。綠色的線是約束秃臣，也就是說(shuō)涧衙，只要正好落在這條綠線上的點(diǎn)才可能是滿(mǎn)足要求的點(diǎn)。如果沒(méi)有這條約束奥此，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)部或者外部，使得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值更大或者更小蠢终，只有到等高線與目標(biāo)函數(shù)的曲線相切的時(shí)候序攘，可能取得最優(yōu)值。
如果我們對(duì)約束也求梯度?g(x,y)寻拂，則其梯度如圖中綠色箭頭所示程奠。很容易看出來(lái)，要想讓目標(biāo)函數(shù)f(x,y)的等高線和約束相切兜喻，則他們切點(diǎn)的梯度一定在一條直線上(f和g的斜率平行)雹锣。
也即在最優(yōu)化解的時(shí)候：?f(x,y)=λ（?g(x,y)-C) （其中?為梯度算子; 即：f(x)的梯度 = λ* g(x)的梯度，λ是常數(shù),可以是任何非0實(shí)數(shù)届搁，表示左右兩邊同向。）
即：▽[f(x,y)+λ(g(x,y)?c)]=0λ≠0
那么拉格朗日函數(shù)： F(x,y)=f(x,y)+λ(g(x,y)?c) 在達(dá)到極值時(shí)與f(x,y)相等泛粹，因?yàn)镕(x,y)達(dá)到極值時(shí)g(x,y)?c總等于零。
min( F(x,λ) )取得極小值時(shí)其導(dǎo)數(shù)為0肮疗，即▽f(x)+▽∑ni=λihi(x)=0晶姊，也就是說(shuō)f(x)和h(x)的梯度共線。
簡(jiǎn)單的說(shuō)伪货，在F(x,λ)取得最優(yōu)化解的時(shí)候们衙，即F(x,λ)取極值（導(dǎo)數(shù)為0，▽[f(x,y)+λ(g(x,y)?c)]=0）的時(shí)候碱呼，f(x)與g(x) 梯度共線蒙挑，此時(shí)就是在條件約束g(x)下，f(x)的最優(yōu)化解愚臀。
-
不等式約束條件
設(shè)目標(biāo)函數(shù)f(x)忆蚀，不等式約束為g(x)，有的教程還會(huì)添加上等式約束條件h(x)姑裂。此時(shí)的約束優(yōu)化問(wèn)題描述如下：
image.png
則我們定義不等式約束下的拉格朗日函數(shù)L馋袜，則L表達(dá)式為：
image.png
其中f(x)是原目標(biāo)函數(shù)，hj(x)是第j個(gè)等式約束條件舶斧，λj是對(duì)應(yīng)的約束系數(shù)欣鳖，gk是不等式約束，uk是對(duì)應(yīng)的約束系數(shù)茴厉。
常用的方法是KKT條件泽台，同樣地，把所有的不等式約束矾缓、等式約束和目標(biāo)函數(shù)全部寫(xiě)為一個(gè)式子L(a, b, x)= f(x) + ag(x)+bh(x)师痕，
KKT條件是說(shuō)最優(yōu)值必須滿(mǎn)足以下條件：
- L(a, b, x)對(duì)x求導(dǎo)為零
- h(x) =0
- a*g(x) = 0
求取這些等式之后就能得到候選最優(yōu)值。其中第三個(gè)式子非常有趣而账，因?yàn)間(x)<=0胰坟，如果要滿(mǎn)足這個(gè)等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來(lái)源泞辐，如支持向量的概念笔横。
接下來(lái)主要介紹KKT條件，推導(dǎo)及應(yīng)用咐吼。詳細(xì)推導(dǎo)過(guò)程如下：
