學習筆記，僅供參考，有錯必糾
轉(zhuǎn)載自：彭一洋

---

最近也在看關(guān)于優(yōu)化的東西，題主在問題補充里問了好多，我暫且以二維空間 [公式] 舉例，從簡單的無約束的優(yōu)化（0梯度條件），到等式約束優(yōu)化(拉格朗日條件)，再到不等式約束優(yōu)化（KKT條件），寫點對于優(yōu)化問題自己能寫的理解，權(quán)當做拋磚引玉。

無約束的優(yōu)化問題

注意我在圖里畫了等高線。此時$f(x)$在局部極小值點$x^{?}=(x_1^{?},x_2^{?})$ 處的梯度必然為0，比較容易理解。這個梯度為零的條件是局部極小值點的必要條件。這樣，優(yōu)化問題的求解變成了對該必要條件解方程組。

帶等式約束的優(yōu)化問題

與無約束的問題不同。我們所要求的極小值點被限制在曲線$h(x)=0$上，我們將$\{x|h(x)=0\}$稱為可行域, 解只能在這個可行域里取。如下圖所示，曲線$h(x)=0$（黑色實曲線）經(jīng)過無約束極小值點（黑點）附近。那么滿足約束的極小值點應(yīng)該與黑點盡可能近。我們將 $f(x)$的等高線不斷放大，直到與曲線$h(x)=0$相切，切點即為所求。相切是關(guān)鍵，是極小值點的必要條件。

如此，帶等式約束的優(yōu)化問題轉(zhuǎn)化為了無約束的優(yōu)化問題，只需要對拉格朗日條件解方程組即可。這里λ就是拉格朗日乘子，有多少個等式約束就有多少個拉格朗日乘子。

帶不等式約束的優(yōu)化問題

當只有一個不等式起作用時, 如我們把問題2里的等式約束$h(x)=0$改為$h(x)\le 0$，如下圖所示，可行域變成了陰影部分，最小值點還是切點，情況和問題2完全一樣，只需要把不等號當做等號去求解即可。

當兩個不等式起作用時，那么問題就來了：

如下圖，當$f(x)$的等高線慢慢擴大時，等高線與可行域(陰影部分)第一次相遇的點是個頂點，2個不等式同時起作用了。滿足約束的最小值點從原來的黑點位置(切點)移動到了紅點位置，現(xiàn)在跟哪條約束函數(shù)曲線都不相切。這時候就需要用到kkt條件了。這里的“條件”是指：某一個點它如果是最小值點的話，就必須滿足這個條件（在含不等式約束的優(yōu)化問題里）。這是個必要條件，前面說的也全部是必要條件。

這個問題的解 $x^{?}$應(yīng)滿足的KKT（卡羅需-庫恩-塔克）條件為：

${\mu }_1\ge 0,{\mu }_2\ge 0$;

$?f(x^{?})+{\mu }_1?g_1(x^{?})+{\mu }_2?g_2(x^{?})=0$;

${\mu }_1{g}_1(x^{?})+{\mu }_2{g}_2(x^{?})=0$

其中，$\mu$叫KKT乘子，有多少個不等式約束就有多少個KKT乘子。加上問題3中的約束部分，就是完整版的KKT條件。對于有等式的情況，你把其中一個不等式約束換成等式，可行域變成了半條曲線，最小值點還是那個紅點，和下面這種情況是一樣的。

有時候，有的不等式約束實際上不起作用，如下面這個優(yōu)化問題：

如下圖的$g_3(x_1,x_2)\le 0$是不起作用的：

對于最小值點$x^{?}$ ,三個不等式約束的不同在于：

這時，這個問題的KKT條件1，2成了：

${\mu }_1\ge 0,{\mu }_2\ge 0,{\mu }_3\ge 0$;

$?f(x^{?})+{\mu }_1?g_1(x^{?})+{\mu }_2?g_2(x^{?})+{\mu }_3?g_3(x^{?})=0$;

條件2中的${\mu }_3?g_3(x^{?})$這一項讓我們很苦惱啊， $g_3(x^{?})$的綠色箭頭跟我們的紅色箭頭沒關(guān)系。要是能令${\mu }_3=0$就好了。加上條件3：

${\mu }_1{g}_1(x^{?})+{\mu }_2{g}_2(x^{?})+{\mu }_3{g}_3(x^{?})=0$

恰好能使${\mu }_3=0$. 由于$g_1(x^{?})=0,g_2(x^{?})=0$，所以前兩項等于0，第三項$g_3(x^{?})<0$, 在條件3的作用下使得${\mu }_3=0$正好滿足需求。

如果再多幾項不起作用的不等式約束，比如$g_4(x)\le 0$。要使${\mu }_1{g}_1(x^{?})+{\mu }_2{g}_2(x^{?})+{\mu }_3{g}_3(x^{?})+{\mu }_4{g}_4(x^{?})=0$，就只能有${\mu }_3{g}_3(x^{?})+{\mu }_4{g}_4(x^{?})=0$.

如果再定義一個拉格朗日函數(shù)：
$$L(x,\mu )=f(x)+{\mu }_1{g}_1(x)+{\mu }_2{g}_2(x)+?$$

最后說明一下，以上所有都是局部極小值點的必要條件。據(jù)此求得的解不一定是局部極小值點（更別提全局了），原因是上圖中我所畫的等高線也許根本就不閉合，也就是說我們一直想要靠近的等高線中間的黑點壓根就是個鞍點或者近似鞍點！

總結(jié)

以上是生活随笔為你收集整理的如何通俗的理解KKT条件的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。