【學界】關於KKT條件的深入探討

03-04

作者簡介： @文雨之本科東北大學自動化專業，然後直接攻博讀的是系統工程專業。目前在東北大學系統工程專業讀博士，在流程工業綜合自動化國家重點實驗室做流程工業裡邊調度問題和運行優化問題。博士剛開始主要接觸了很多Numerical optimization， Convex optimization，Nonlinear programming的知識，用來解決實際工業過程中的優化問題。隨著近幾年來，人工智慧機器學習火了起來，逐漸研究的重心也從數學優化轉到機器學習相關領域了，但是我一直還是認為優化是自己的老本行，也一直從優化的角度去看待機器學習的問題去嘗試做一些新的思考。
歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。
敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：
『運籌OR帷幄』大數據人工智慧時代的運籌學--知乎專欄

KKT（Karush-Kuhn-Tucker）條件作為帶約束可微分優化問題的最優性條件，佔據這非常重要的地位。目前對於KKT條件的介紹網路上也有不少資料。這篇文章主要的目的一個是把這些資料梳理出來構成一個相對清晰的脈絡，另一個是在講述過程中加入了一些自己的思考用來補充一下大家對KKT的認識。同時也是通過自己的思考起到一個拋磚引玉的效果，讓大家意識到如此常見和簡單的一個KKT條件，其實也不是那麼簡單。最後簡單闡述了一下最優性條件為啥那麼重要，以及KKT與凸優化的關係。為了簡單方便起見，在無特殊說明的情況下本文中「最優」，「最優性條件」都指的是局部最優。若想進一步了解本文用到的運籌優化領域相關概念可以參考【學界】人工智慧的「引擎」--運籌學，一門建模、優化、決策的科學

0. KKT 條件的歷史背景

KKT條件的發現還有一段歷史小插曲。1951年Kuhn和Tucker發現了KKT條件並撰寫了論文將其正式發表出來[1]，引起了很多學者的重視。自此之後一些學者發現早在1939年Karush在其碩士學位論文[2]裡邊已經給出了KKT條件，只是由於當時沒有引起研究者的廣泛關注而已。因此Kuhn ，Tucker，Karush 三位都作為獨立發現KKT條件的學者，這個最優性條件就以他們三個人的名字來命名。

1. 無約束優化問題最優性條件

我們先從無約束優化問題的最優性條件開始談起，有如下無約束的優化問題

$[mathop {min }limits_x fleft( x ight)]$

若 $[fleft( x ight)]$ 可微，則其最優解的一階必要條件為

$[ abla fleft( x ight) = 0]$

這個條件的推導過程可以由泰勒展開得到[3, page 16]，這裡不再贅述。

2. 有約束優化問題最優性條件

下面考慮如下帶約束的優化問題

$[egin{array}{l} mathop {min }limits_x fleft( x ight)\ s.t.;;;{g_i}left( x ight) le 0,;;i = 1,2, cdots ,m\ ;;;;;;;{h_i}left( x ight) = 0,;;i = 1,2, cdots ,n end{array}]$ （1.1）

其中 $[f,{g_1}, cdots ,{g_m},{h_1}, cdots ,{h_n}]$ 可微且一階導數連續，存在非負實數 $[{mu _1}, cdots {mu _m}]$ 和實數 $[{lambda _1}, cdots ,{lambda _n}]$ ，若 $[{x^*}]$ 為局部最優解則以下條件成立：

$[egin{array}{l} abla fleft( {{x^*}} ight) + sumlimits_{i = 1}^m {mu _i^*{g_i}left( {{x^*}} ight) + sumlimits_{i = 1}^n {lambda _i^*{h_i}left( {{x^*}} ight)} } = 0\ {h_i}left( {{x^*}} ight) = 0,;;;;;;;i = 1,2, cdots ,n\ {g_i}left( {{x^*}} ight) le 0,;;;;;;;i = 1,2, cdots ,m\ mu _i^* ge 0,;;;;;;;;;;;;;i = 1,2, cdots ,m\ mu _i^*{g_i}left( {{x^*}} ight) = 0,;;;i = 1,2, cdots ,m end{array}]$

至於該條件如何被推導出可以參考文末的參考文獻[3, page 210]。你也可以將無約束優化問題的最優性條件當作KKT的特殊情況。一般情況下，我們認為KKT條件是帶約束最優化問題的必要條件。這裡需要重申一點就是最後一個條件 $[mu _i^*{g_i}left( {{x^*}} ight) = 0]$ ，這意味著 $[mu _i^* = 0,{g_i}left( {{x^*}} ight) = 0]$ 這兩者中必有一個為0，當 $[{g_i}left( {{x^*}} ight) = 0]$ 時該約束為起作用約束，定義 $[Ileft( {{x^*}} ight)]$ 為起作用約束集合。當 $[mu _i^* = 0]$ 時該約束為不起作用約束，也就是說此時 $[{{x^*}}]$ 並未到達邊界上，因此即使去掉該約束也不會影響最優解的取值。

貌似這是一般情況下我們熟知的KKT條件，事實上，上面陳述的KKT條件並不完全正確（嚴謹），還缺少一個regularity條件。

regularity 條件（也被成為正則性條件或者約束規範）如下

考慮（1.1）的優化問題，其中 $[f,{g_1}, cdots ,{g_m},{h_1}, cdots ,{h_n}]$ 可微且一階導數連續，可行解 $[{x^*}]$ 滿足 $[left{ { abla {g_i}left( {{x^*}} ight):i in Ileft( {{x^*}} ight)} ight}igcup {left{ { abla {h_j}left( {{x^*}} ight):j = 1,2, cdots ,n} ight}} ]$ 是線性獨立的。

也就是說在使用KKT條件之前需要驗證regularity條件，否則就無法保證KKT條件給出的結論一定成立。

3. 缺少regularity條件KKT還是最優解的必要條件嗎？

若滿足regularity條件，KKT就是最優解的必要條件。所謂必要條件的意思是滿足KKT條件的不一定是最優解（例如鞍點就滿足KKT，但鞍點就不是最優解），但是如果不滿足KKT條件就一定不是最優解。本章我會用一個具體的例子來說明，缺少了regularity條件，KKT條件就並非最優解的必要條件。下面我就來展開分析一下這種特殊情況

$[egin{array}{l} mathop {min }limits_x x\ s.t.;;{x^2} le 0 end{array}]$

$[{x^*} = 0]$ 為該約束優化問題的局部最優解但其並不滿足regularity條件。

因為 ${ m{{ }} abla {{ m{g}}_{ m{i}}}{ m{(}}{{ m{x}}^{ m{*}}}{ m{): i}} in { m{I(}}{{ m{x}}^{ m{*}}}{ m{)} }} = { m{{ }} abla {{ m{g}}_{ m{i}}}{ m{(}}{{ m{x}}^{ m{*}}}{ m{):}}{{ m{g}}_{ m{i}}}{ m{(}}{{ m{x}}^{ m{*}}}{ m{)}} = { m{0} }} = { m{{ 0} }}$ 是一個線性相關集。

在該問題裡邊目標函數 $[ abla fleft( {{x^*}} ight) = 1]$ ， $[gleft( {{x^*}} ight) = 0]$ ，同時等式約束也沒有。顯而易見KKT的第一個等式 $[ abla fleft( {{x^*}} ight) + sumlimits_{i = 1}^m {mu _i^*{g_i}left( {{x^*}} ight) + sumlimits_{i = 1}^n {lambda _i^*{h_i}left( {{x^*}} ight)} } = 0]$ 是不可能成立。

進一步分析一下，造成其不滿足KKT條件的原因是什麼呢？是由於約束過於苛刻了，導致整個可行域只有一個單點。此時該約束優化問題的最優解無論其目標函數是什麼樣，其最優解都是 $[{x^*} = 0]$ ，也就是說其最優解與目標函數沒有任何關係。正是這種非常罕見的退化情況導致了KKT條件無法適用。

學過運籌優化的同學應該對另外一個和KKT很相近的定理有記憶，它就是Fritz John 條件。考慮（1.1）的優化問題，其中 $[f,{g_1}, cdots ,{g_m},{h_1}, cdots ,{h_n}]$ 可微且一階導數連續，存在不全為0的非負實數 $[{mu _0},{mu _1}, cdots {mu _m}]$ 和實數 $[{lambda _1}, cdots ,{lambda _n}]$ ，若 $[{x^*}]$ 為局部最優解則以下條件成立：

$[egin{array}{l} {mu _0} abla fleft( {{x^*}} ight) + sumlimits_{i = 1}^m {mu _i^*{g_i}left( {{x^*}} ight) + sumlimits_{i = 1}^n {lambda _i^*{h_i}left( {{x^*}} ight)} } = 0\ {h_i}left( {{x^*}} ight) = 0,;;;;;;;i = 1,2, cdots ,n\ {g_i}left( {{x^*}} ight) le 0,;;;;;;;i = 1,2, cdots ,m\ mu _i^* ge 0,;;;;;;;;;;;;;i = 1,2, cdots ,m\ mu _i^*{g_i}left( {{x^*}} ight) = 0,;;;i = 1,2, cdots ,m end{array}]$

仔細對比KKT條件和Fritz John條件，發現兩者的區別是Fritz John conditions多了一個對目標函數的乘子，恰恰可以把上面那種退化的情況涵蓋進去。如下式所示：

$[{mu _0} abla fleft( {{x^*}} ight) + sumlimits_{i = 1}^m {mu _i^*{g_i}left( {{x^*}} ight) + sumlimits_{i = 1}^n {lambda _i^*{h_i}left( {{x^*}} ight)} } = 0]$

針對上面那個退化情況，只需讓 $[{mu _0} = 0]$ 即可。 $[{mu _0} = 0]$ 實際上和 $[lambda { m{ = 0}}]$ 的意義是相似的，說明目標函數是不起作用的，也就是無論目標函數怎麼變化也對最優解沒有影響。反過來再對照我們構造的特殊情況確實也是印證了上面所說的這一點。由此我們得到了對於我們舉出的退化問題，存在 $[{x^*} = 0]$ 為其最優解，但是卻不滿足KKT條件的情況。那麼去掉regularity條件的KKT條件是最優解的必要條件實際上是不成立的。實際上Fritz John條件才是真正的必要條件，KKT是刨除了不滿足regularity條件情況的前提下才能稱為最優解的必要條件。易知，若 $[{mu _0} e 0]$ 我們在Fritz John條件等式兩邊同時除以 $[{mu _0}]$ 就可以得到KKT條件。

因此在應用KKT條件的時候，一定需要首先檢驗regularity條件。

4. KKT(最優性條件)為什麼這麼重要？

我們經常會提到最優性條件，也經常會用到最優性條件，為啥它就那麼重要呢？如果一個優化問題有最優性條件的話，那這個優化問題的性質實際上是比較好的。我目前能想到的是以下兩個原因：

1 通過最優性條件可以比較容易的驗證任意的一個解是不是最優解，例如KKT條件，它是最優解的必要條件，它就可以把可行域裡邊很多的不是最優解的解輕鬆的排除掉，讓我們僅僅在滿足必要條件（KKT條件）的解裡邊進一步尋找真正的最優解。混合整數規劃問題比較困難的原因之一就是很難找到最優性條件，很多情況下即使驗證一個解是不是最優解都比較困難。

2 最優性條件可以指導演算法的設計。例如對於無約束可微分的優化問題，我們採用梯度法，牛頓法，擬牛頓法等，其收斂性的證明都是證明最終演算法能收斂到導數等於0的地方。所以演算法的設計都是考慮如何能夠收斂到最優性條件去，這樣在很多情況下比直接去求解極值要容易的多。

5. KKT和凸優化的關係是什麼？

KKT主要是針對帶約束的可微分的優化問題，凸優化研究的對象是目標函數為凸函數，約束為凸集的優化問題。因此這兩者研究的對象，有交集，也各有不同。

第一類問題為兩類問題的交集即帶約束的可微分凸優化問題，這類問題目前已經被很好的解決了，它同時具備兩類問題的性質，凸優化和可微分性，讓原來KKT從局部最優解的必要條件變為全局最優解的充要條件。

第二類問題是凸優化但是不可微分，這類問題也較為常見，在拉格朗日鬆弛演算法中，對偶問題一般都是不可微分的凸優化問題，因為不可微分，傳統的基於梯度的方法就不適用了，一般採用次梯度的方法，主要難點在於次梯度如何確定，由於次梯度不唯一，如何確定一個簡單有效的次梯度也是一個問題。

第三類問題是可微分的但不是凸優化的，這類問題也很多，一般這類問題都可以採用基於梯度的演算法來求解，例如對神經網路的訓練多數就屬於這類問題。採用梯度法僅僅能保證收斂到局部最優的必要條件而已。因此該類問題的受困於陷入鞍點和全局最優的尋找是很困難的。

總結

1 去掉regularity條件的KKT條件嚴格來講並非最優解的必要條件。

2 有最優性條件對優化問題而言是一個較好的性質。

參考文獻

[1] Kuhn, H. W.; Tucker, A. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492. MR 0047303.

[2] W. Karush (1939). "Minima of Functions of Several Variables with Inequalities as Side Constraints". M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.

[3] Amir Beck, Introduction to NLP: theory, algorithms, and applications with Matlab, 2014.

在此感謝『運籌OR帷幄』審稿人對本文提出了寶貴的意見。

『運籌OR帷幄』審稿人 @Xiaoxi Li，巴黎六大數學博士、武漢大學助理教授，研究方向：博弈論。

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

運籌學/控制論/隨機優化愛好者，歡迎加qq群：686387574

人工智慧愛好者，歡迎加qq群： 685839321

最後敬請關注和擴散本專欄及同名公眾號，會陸續發布運籌學、人工智慧中優化理論相關乾貨及行業動態：『運籌OR帷幄』大數據和人工智慧時代下的運籌學 - 知乎專欄