拉格朗日乘數(shù)法無(wú)疑是最優(yōu)化理論中最重要的方法。但是網(wǎng)上沒(méi)有一篇文章全面介紹了整個(gè)方法。為此，邊肖整理了以下文章，希望能贏得大家的好評(píng)。

拉格朗日乘子法和KKT條件是求解帶約束優(yōu)化問(wèn)題的兩種非常重要的方法。對(duì)于等式約束的優(yōu)化問(wèn)題，可以使用拉格朗日乘子法來(lái)尋找最優(yōu)值。如果存在不等式約束，可以應(yīng)用KKT條件來(lái)求解。當(dāng)然，這兩種方法得到的結(jié)果只是必要條件，只有當(dāng)它們是凸函數(shù)時(shí)，才能保證它們是充分必要條件。

KKT條件是拉格朗日乘數(shù)法的推廣。以前學(xué)習(xí)的時(shí)候只知道直接應(yīng)用兩種方法，不知道拉格朗日乘數(shù)和KKT條件為什么能起作用，為什么要用這種方式得到最優(yōu)值？

本文首先介紹了什么是拉格朗日乘數(shù)和KKT條件。然后我們開(kāi)始講為什么要用這種方式去尋找最優(yōu)值。

1.拉格朗日乘數(shù)和KKT條件

一般我們需要解決的優(yōu)化問(wèn)題如下:

(一)無(wú)約束優(yōu)化問(wèn)題，可以寫成:

最小f(x)；

(ii)等式約束的優(yōu)化問(wèn)題可以寫成:

最小f(x)，

s . t . h _ I(x)= 0；i =1，...，n

(iii)具有不等式約束的優(yōu)化問(wèn)題可以寫成:

最小f(x)，

s.t. g_i(x) <。= 0;i =1，...，n

h _ j(x)= 0；j =1。...，m

費(fèi)馬定理常用于類(I)的優(yōu)化問(wèn)題，即通過(guò)計(jì)算f(x)的導(dǎo)數(shù)，然后使其為零，可以得到候選最優(yōu)值，并在這些候選值中進(jìn)行驗(yàn)證；如果是凸函數(shù)，可以保證是最優(yōu)解。

對(duì)于(ii)優(yōu)化問(wèn)題，常用的方法是拉格朗日乘子，即把方程約束h_i(x)寫成一個(gè)帶系數(shù)和f(x)的公式，稱為拉格朗日函數(shù)，系數(shù)稱為拉格朗日乘子。通過(guò)拉格朗日函數(shù)取各變量的導(dǎo)數(shù)并使之為零，就可以得到候選值集，然后通過(guò)驗(yàn)證就可以得到最優(yōu)值。

KKT條件常用于(ⅲ)優(yōu)化問(wèn)題。同樣，我們把所有的等式、不等式約束和f(x)寫成公式，也叫拉格朗日函數(shù)，系數(shù)也叫拉格朗日乘數(shù)。通過(guò)一些條件，我們可以找到最優(yōu)值的必要條件，這就是所謂的KKT條件。

拉格朗日乘數(shù)法(拉格朗日乘數(shù))

關(guān)于等式約束，我們可以通過(guò)一個(gè)拉格朗日系數(shù)a把等式約束和目標(biāo)函數(shù)結(jié)合成一個(gè)公式L(a，x) = f(x)+a*h(x)，這里把a(bǔ)和h(x)看作向量形式，a是橫量，h(x)是列向量。寫這個(gè)的原因是csdn很難寫數(shù)學(xué)公式，所以只能將就了。

然后得到最優(yōu)值，取L(a，x)的導(dǎo)數(shù)，每個(gè)參數(shù)取0，聯(lián)立方程即可得到。這是高等數(shù)學(xué)里講過(guò)的，但是不講為什么這樣做也是可以的。后面簡(jiǎn)單介紹一下思路。

(b) KKT條件

對(duì)于不等式約束的優(yōu)化問(wèn)題，如何得到最優(yōu)值？常用的方法是KKT條件。同樣，所有不等式約束、等式約束和目標(biāo)函數(shù)都寫成公式L(a，b，x)= f(x)+a*g(x)+b*h(x)。KKT條件意味著最優(yōu)值必須滿足以下條件:

1.l (a，b，x)對(duì)x的導(dǎo)數(shù)為零；

2.h(x)= 0；

3.a * g(x)= 0；

求解這三個(gè)方程后，就可以得到候選最優(yōu)值。第三個(gè)方程非常有趣，因?yàn)間 (x)

2.拉格朗日乘數(shù)和KKT條件為什么能得到最優(yōu)值？

為什么要得到最好的價(jià)值？先說(shuō)拉格朗日乘數(shù)法。設(shè)想我們的目標(biāo)函數(shù)z = f(x)，x)，其中x是向量，z取不同的值，相當(dāng)于投影到x組成的平面(曲面)上，也就是變成一條輪廓線。如下圖，目標(biāo)函數(shù)為f(x，y)，其中x為標(biāo)量，虛線為等高線。

現(xiàn)在我們假設(shè)我們的約束g(x)=0，x是一個(gè)向量，是x形成的平面或曲面上的一條曲線，我們假設(shè)g(x)與等高線相交，交點(diǎn)是一個(gè)同時(shí)滿足等式約束和目標(biāo)函數(shù)的值，但肯定不是最優(yōu)值，因?yàn)橄嘟灰馕吨@條等高線內(nèi)或外一定有其他等高線，這使得新等高線與目標(biāo)函數(shù)的交點(diǎn)變大或變小。只有當(dāng)輪廓線與目標(biāo)函數(shù)的曲線相切時(shí)，才有可能得到最優(yōu)值，如下圖所示，即輪廓線的法向量與目標(biāo)函數(shù)的曲線在該點(diǎn)必須有相同的方向。

所以最優(yōu)值必須滿足:f(x)的梯度= a * g(x)的梯度，a為常數(shù)，表示左右兩邊同向。這個(gè)方程是L(a，x)對(duì)參數(shù)求導(dǎo)的結(jié)果。(不知道以上描述是否清楚。如果離我的物理位置近，直接來(lái)找我。我會(huì)當(dāng)面解釋，更好理解。注意:下圖來(lái)自wiki。).

KKT條件是滿足強(qiáng)對(duì)偶條件的最優(yōu)化問(wèn)題的必要條件，可以理解為:我們要求min f (x)，l (a，b，x) = f (x)+a * g (x)+b * h (x)，a >；=0，我們可以把f(x)寫成max_{a，b} L(a，b，x)。

為什么？G (x)

如果用對(duì)偶表達(dá)式:max_{a，b} min_x L(a，b，x)，由于我們的優(yōu)化滿足強(qiáng)對(duì)偶(強(qiáng)對(duì)偶是指對(duì)偶公式的最優(yōu)值等于原問(wèn)題的最優(yōu)值)，所以在得到最優(yōu)值x0的條件下滿足f (x0) = max _ {a，b} min_x L

f(x0) = max_{a，b} min_x L(a，b，x) = max_{a，b } min _ x f(x)+a * g(x)+b * h(x)= max _ { a，b} f(x0)+a*g(x0)+b*h(x0) = f(x0)

可以看出，上述黑化的地方本質(zhì)上是指min_x f(x)+a*g(x)+b*h(x)在x0處得到最小值。利用費(fèi)馬定理，也就是說(shuō)對(duì)于函數(shù)f(x)+a*g(x)+b*h(x)，導(dǎo)數(shù)必須等于零，即f(x)。

這是kkt條件中的第一個(gè)條件:L(a，b，x)對(duì)x的導(dǎo)數(shù)為零。

前面解釋過(guò)，a*g(x) = 0，那么kkt條件的第三個(gè)條件，當(dāng)然是已知條件h(x)=0必須滿足。以上所有解釋表明，滿足強(qiáng)對(duì)偶條件的優(yōu)化問(wèn)題的最優(yōu)值必須滿足KKT條件，即上述三個(gè)條件。KKT條件可以看作是拉格朗日乘數(shù)法的推廣。

聲明:本文轉(zhuǎn)載于網(wǎng)絡(luò)，版權(quán)歸原作者所有。如果涉及到作品的版權(quán)問(wèn)題，請(qǐng)聯(lián)系我們，我們會(huì)根據(jù)您提供的版權(quán)證明確認(rèn)版權(quán)并支付報(bào)酬或刪除內(nèi)容。