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

作者：由王源發表于書法時間：2018-02-11

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 f\left( x \right)$

若

$f\left( x \right)$

可微，則其最優解的一階必要條件為

$\nabla f\left( x \right) = 0$

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

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

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

$\begin{array}{l} \mathop {\min }\limits_x f\left( x \right)\\ s.t.\;\;\;{g_i}\left( x \right) \le 0,\;\;i = 1,2, \cdots ,m\\ \;\;\;\;\;\;\;{h_i}\left( x \right) = 0,\;\;i = 1,2, \cdots ,n \end{array}$

（1。1）

其中 #FormatImgID_5# 可微且一階導數連續，存在非負實數 #FormatImgID_6# 和實數 #FormatImgID_7# ，若 #FormatImgID_8# 為區域性最優解則以下條件成立：

$\begin{array}{l} \nabla f\left( {{x^*}} \right) + \sum\limits_{i = 1}^m {\mu _i^*\nabla{g_i}\left( {{x^*}} \right) + \sum\limits_{i = 1}^n {\lambda _i^*\nabla{h_i}\left( {{x^*}} \right)} } = 0\\ {h_i}\left( {{x^*}} \right) = 0,\;\;\;\;\;\;\;i = 1,2, \cdots ,n\\ {g_i}\left( {{x^*}} \right) \le 0,\;\;\;\;\;\;\;i = 1,2, \cdots ,m\\ \mu _i^* \ge 0,\;\;\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,m\\ \mu _i^*{g_i}\left( {{x^*}} \right) = 0,\;\;\;i = 1,2, \cdots ,m \end{array}$

至於該條件如何被推匯出可以參考文末的參考文獻［3， page 210］。你也可以將無約束最佳化問題的最優性條件當作KKT的特殊情況。一般情況下，我們認為KKT條件是帶約束最最佳化問題的必要條件。這裡需要重申一點就是最後一個條件

$\mu _i^*{g_i}\left( {{x^*}} \right) = 0$

，這意味著

$\mu _i^* = 0,{g_i}\left( {{x^*}} \right) = 0$

這兩者中必有一個為0，當

${g_i}\left( {{x^*}} \right) = 0$

時該約束為起作用約束，定義

$I\left( {{x^*}} \right)$

為起作用約束集合。當

$\mu _i^* = 0$

時該約束為不起作用約束，也就是說此時

${{x^*}}$

並未到達邊界上，因此即使去掉該約束也不會影響最優解的取值。

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

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

考慮（1.1）的最佳化問題，其中 #FormatImgID_16# 可微且一階導數連續，可行解 #FormatImgID_17# 滿足 #FormatImgID_18# 是線性獨立的。

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

。

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

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

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

#FormatImgID_20# 為該約束最佳化問題的區域性最優解但其並不滿足regularity條件。

因為 #FormatImgID_21# 是一個線性相關集。

在該問題裡邊目標函式

$\nabla f\left( {{x^*}} \right) = 1$

，

$g\left( {{x^*}} \right) = 0$

，同時等式約束也沒有。顯而易見KKT的第一個等式

$\nabla f\left( {{x^*}} \right) + \sum\limits_{i = 1}^m {\mu _i^*\nabla{g_i}\left( {{x^*}} \right) + \sum\limits_{i = 1}^n {\lambda _i^*\nabla{h_i}\left( {{x^*}} \right)} } = 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^*}$

為區域性最優解則以下條件成立：

$\begin{array}{l} {\mu _0}\nabla f\left( {{x^*}} \right) + \sum\limits_{i = 1}^m {\mu _i^*\nabla{g_i}\left( {{x^*}} \right) + \sum\limits_{i = 1}^n {\lambda _i^*\nabla{h_i}\left( {{x^*}} \right)} } = 0\\ {h_i}\left( {{x^*}} \right) = 0,\;\;\;\;\;\;\;i = 1,2, \cdots ,n\\ {g_i}\left( {{x^*}} \right) \le 0,\;\;\;\;\;\;\;i = 1,2, \cdots ,m\\ \mu _i^* \ge 0,\;\;\;\;\;\;\;\;\;\;\;\;\;i = 1,2, \cdots ,m\\ \mu _i^*{g_i}\left( {{x^*}} \right) = 0,\;\;\;i = 1,2, \cdots ,m \end{array}$

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

${\mu _0}\nabla f\left( {{x^*}} \right) + \sum\limits_{i = 1}^m {\mu _i^*\nabla{g_i}\left( {{x^*}} \right) + \sum\limits_{i = 1}^n {\lambda _i^*\nabla{h_i}\left( {{x^*}} \right)} } = 0$

針對上面那個退化情況，只需讓

${\mu _0} = 0$

即可。

${\mu _0} = 0$

實際上和

$\lambda {\rm{ = 0}}$

的意義是相似的，說明目標函式是不起作用的，也就是無論目標函式怎麼變化也對最優解沒有影響。反過來再對照我們構造的特殊情況確實也是印證了上面所說的這一點。由此我們得到了對於我們舉出的退化問題，存在

${x^*} = 0$

為其最優解，但是卻不滿足KKT條件的情況。那麼去掉regularity條件的KKT條件是最優解的必要條件實際上是不成立的。實際上Fritz John條件才是真正的必要條件，KKT是刨除了不滿足regularity條件情況的前提下才能稱為最優解的必要條件。易知，若

${\mu _0} \ne 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。

在此感謝 @Xiaoxi Li，巴黎六大數學博士、武漢大學助理教授對本文提出的意見。

標簽： KKT 條件最優最優性最佳化

上一篇:簡單高效的直播伺服器開源專案推薦

下一篇：為什麼有那麼多人迷戀韓劇日劇美劇，卻不會韓語日語英語？

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

猜你喜歡

我今年28歲想報考軍隊文職對年齡的要求是怎樣的？

中國未來會因為男女比例失調會造成什麼後果？

做100次機器學習（不同訓練集測試集的劃分），選取測試集auc最高的模型做為最佳模型，這樣合理嗎?

人生，區域性最優與全域性最優

在中國為什麼很多時候，一個行業不是追求帕累托最優而是反其道而行之？