KKT條件詳解

主要參考這篇文章和這個知乎回答。

KKT最優(yōu)化條件是Karush[1939]，以及Kuhn和Tucker[1951]先后獨立發(fā)表出來的。這組最優(yōu)化條件在Kuhn和Tucker發(fā)表之后才逐漸受到重視，因此許多情況下只記載成庫恩塔克條件（Kuhn-Tucker conditions)

它是非線性規(guī)劃領(lǐng)域的重要成果，是判斷某點是極值點的必要條件。對于凸規(guī)劃，KKT條件就是充要條件了，只要滿足則一定是極值點，且一定得到的是全局最優(yōu)解（凸問題）。

KKT條件的引入推廣了拉格朗日乘子法，拉格朗日乘數(shù)法原本只是解決等式約束下的優(yōu)化問題，本科的高數(shù)里就講了（我竟讀研了才學(xué)懂，慚愧），而引入KKT條件的拉格朗日乘子法可用于更普遍的有不等式約束的情況。

（一）問題模型

“等式約束+不等式約束” 優(yōu)化問題是最復(fù)雜也最常見的一種模型。問題建模為：
min ? f ( x ) s . t . h k ( x ) = 0 , g j ( x ) ≤ 0 j = 1 , 2 … , n ; k = 1 , 2 … , l min f(x) quad s.t.h_k(x)=0quad,quad g_j(x)leq0quad j=1,2ldots,n;k=1,2ldots,lminf(x)s.t.hk?(x)=0,gj?(x)≤0j=1,2…,n;k=1,2…,l
思路是要把問題轉(zhuǎn)化為無約束的簡單優(yōu)化問題，分為兩步：

先把不等式約束條件轉(zhuǎn)化為等式約束條件。 how？→ o→引入松弛變量，即KKT乘子
再把等式約束轉(zhuǎn)化為無約束優(yōu)化問題。 how?→ o→引入拉格朗日乘子

---

（二）一點鋪墊
后面要用這個結(jié)論：

實質(zhì)上，KKT條件描述的是：這個點已經(jīng)是可行域（滿足所有約束條件的n維空間）的邊界了，再走一點就不滿足約束條件了。顯然，最優(yōu)解一定在可行域的邊界上的，以初中學(xué)的線性規(guī)劃作為簡單的例子，

這張圖的紫色區(qū)域就是四個不等式約束限定的可行域，如果求z=x+2y的最大值，結(jié)果當(dāng)然是紅星點取得最大值，總之極值點應(yīng)該在可行域的邊界，這在自變量多的高維可行域空間也是如此，只是不好畫圖直觀去看了。

---

（三）KKT到底是什么
KKT條件就是說：
如果一個點x ? x^*x?是滿足所有約束的極值點，那么
{ ? f ( x ? ) + ∑ k λ k ? h k ( x ? ) + ∑ j μ j ? g j ( x ? ) = 0 ( 1 ) μ j ≥ 0 ( 2 ) μ j g j ( x ? ) = 0 ( 3 ) g j ( x ? ) ≤ 0 ( 4 ) left{

?f(x?)+∑kλk?hk(x?)+∑jμj?gj(x?)μjμjgj(x?)gj(x?)=≥=≤0(1)0(2)0(3)0(4)?f(x?)+∑kλk?hk(x?)+∑jμj?gj(x?)=0(1)μj≥0(2)μjgj(x?)=0(3)gj(x?)≤0(4)

ight.?????????????????f(x?)+k∑?λk??hk?(x?)+j∑?μj??gj?(x?)μj?μj?gj?(x?)gj?(x?)?=≥=≤?0(1)0(2)0(3)0(4)?
下面進行條件的解讀：

(1) 極值點處函數(shù)的梯度是約束條件梯度的線性組合；只有滿足g j ( x ? ) = 0 g_j(x^*)=0gj?(x?)=0的那些不等式約束的梯度才會出現(xiàn)在加權(quán)式中，才有資格給人加權(quán)。

(2) 不等式約束的權(quán)值（KKT乘子）必須大于等于0，因為f(x) 和g(x)的梯度方向必須相反。
解釋如下：

假設(shè)某問題的可行域就是（b）圖畫的這樣，僅為便于理解哈，實際可行域不一定必須長成這樣。

前面說了，極值點肯定往可行域的邊界靠，肯定不會在可行域中間某處，所以邊界上極值點處的函數(shù)值自然比可行域內(nèi)的函數(shù)值小（這里最小化目標(biāo)函數(shù)，如果是最大化，就是邊界比里面大了），所以極值點處函數(shù)的梯度方向（函數(shù)值增大最快的方向）是向里面的；

而對于約束條件，可行域里的值比邊界要小，所以極值點處g(x)的梯度方向朝外面！！

結(jié)了，二者必然方向相反，所以KKT乘子必然為正。

從這個推導(dǎo)過程你應(yīng)該也能明白為啥等式約束下不要求拉格朗日乘子必須為正了。
等式約束的權(quán)值（拉格朗日乘子）的正負無要求

(3) 若某個不等式約束在極值點取值嚴格小于0，則這個約束條件無效，就是說有沒有這個約束根本影響不了結(jié)果，其KKT乘子為0；

若極值點處不等式約束取值等于0，這個約束就是有效的，可行域的邊界的構(gòu)建就有它出的一份力，則其KKT乘子為正。

這也是KKT乘子為什么又被稱為松弛變量的原因，因為它讓≤ leq≤變成了= ==，把不等式約束變?yōu)榱说仁郊s束，通過它的引入使得約束變得簡單了。

整個可行域是由g j ( x ) ≤ 0 g_j(x)leq0gj?(x)≤0和h k ( x ) = 0 h_k(x)=0hk?(x)=0圍成的，但實際上有些不等式約束沒對邊界的形成做出貢獻，就對函數(shù)在極值點處的梯度無貢獻（都沒在邊界肯定貢獻不了梯度了），所以根本不分配乘子。

總之，拉格朗日乘子法和KKT條件也算是take me a whole day了，從之前上課一直云里霧里乘飛機到現(xiàn)在寫完博客腦子像漿糊，算是基本理清了，這篇講KKT的文章估計讀者會看的很暈，可能沒完全講清楚，但理解KKT，重點還是要從幾何的角度去想，有那么點只可意會不可言傳或者不太好言傳的味道。我就是看一大堆博客回答受到啟發(fā)（暈乎）了以后，想到極值點一定在可行域的邊界，從而對三個KKT條件進行了邏輯上串得起來說得通的解讀的。

總結(jié)

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

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