直觀理解KKT條件

2020-12-06 AI火箭營

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

庫恩塔克條件(Kuhn-Tucker conditions)是非線性規劃領域裡最重要的理論成果之一，是確定某點為極值點的必要條件。如果所討論的規劃是凸規劃，那麼庫恩-塔克條件也是充分條件。

本文不對數學公式進行詳細推導，而是從直觀上對KKT條件進行理解。當然KKT條件與拉格朗日乘子是相關聯的，看完本文後，可以參閱相關資料。

無約束優化問題的極值（函數的最大值/最小值）通常發生在斜率為零的點上。

因此，為了找到極值，我們只需要搜索斜率為零的點。 我們可以用很好的數學形式表達這個屬性。

如果 x* 是無約束優化問題的極值， 那麼

▽f(x*)=0

等式約束的優化問題

如果x*是等式約束的優化問題的極值, 那麼

▽f(x*)=λ×▽g(x*)

g(x*)=0

不等式約束的優化問題

如果x*是不等式約束的優化問題的極值, 那麼,

KKT條件:

原可行性:g(x*)≤0 對偶可行性: α≥0 互補鬆弛條件:αg(x*)=0 拉格朗日平穩性: ▽f(x*)=α×▽g(x*)為了找到具有不等式約束的優化問題的極值，我們需要搜索必須滿足所有KKT條件的點(x*)

KKT條件直觀理解

1.拉格朗日平穩性：下面顯示了具有等式約束的優化問題的等高線圖（它是通過繪製2D格式上的目標函數值的常量切片來表示3D表面的圖）。 分析結束後，你會意識到為什麼我選擇了一個等式約束來解釋拉格朗日平穩性條件。

從等高線圖中，我們可以推斷出上述問題只發生了兩種可行點：1、切點2、交點。 切點是水平曲線（等高線）和約束線彼此相切的點。 交點是水平曲線和約束線相交的點。

在等高線圖中，如果從交叉點（沿約束線）向左移動，則目標函數值會增加。 它表明該問題在這方面有改進的餘地。 同樣，如果從交叉點向右移動，我們的目標函數值會減小。 但是，對於上圖中的切線點，從切線點向右或向左移動只會降低目標函數值。這意味著約束優化問題的極值總是落在切點上。

結論1：約束優化問題的極值總是發生在切點上。

我們知道函數的梯度指向函數增加最大的方向。在下面的等高線圖中，從一個水平曲線移動到另一個水平曲線的最短路徑是垂直方向，水平曲線與函數中沒有立即變化的方向相切。 這意味著任何點處函數的梯度都垂直於該點的函數水平曲線。

結論2：函數的梯度和函數的水平曲線的相切是正交的

通過結合結論1和2，我們可以得出結論，約束的梯度（▽g）和目標函數的梯度（▽f）在極值處（切線點）方向是相同或者相反的。 表達如下：

▽f(x*)=α×▽g(x*)

2. 對偶鬆弛(α≥0)

α被稱為KKT乘子或對偶變量（如果我們將原始問題轉換為對偶形式，KKT乘子將成為對偶形式的變量）。在解釋KKT乘子只允許非負值的原因之前，讓我告訴KKT乘子符號在約束優化問題中的影響是什麼.

如果α≥0, 那麼 ▽f 和 ▽g 方向是同向的 (▽f(x*)=α×▽g(x*)).

同樣，如果α≤0, 那麼▽f 和▽g方向是相反的。

例如:

Max 2x22y2 (1)

s.t. x+y≤1

上述問題的最優解是4/3 ，

當x*=2/3 , y*=1/3 and α=4/3。

正如我們在上文看到的那樣，拉格朗日乘子對具有等式約束的優化問題沒有任何符號限制。但是，對於具有不等式約束的優化問題，KKT乘子是有符號限制的(α≥0)。 你可能會懷疑我們為什麼對不等式約束有這個符號限制。在講KKT乘子只取非負值的原因之前，咱們先來分析下可行域。

· g(x,y)=0(x+y1=0):可行域僅是一條直線

· g(x,y)≥0:直線上方都是可行域。

· g(x,y)≤0:直線的下方是可行域。

結論3：約束梯度（▽g）始終指向約束控制的可行區域（g（x，y）≥0，g（x，y）≤0方向分別相反）

現在，你可能會理解上述問題中的KKT乘子，只有在可行區域翻轉時才會出現負號(i.e.,x+y≥1)。

如果發生這種情況，約束不會對目標函數產生任何影響。 這就像解決一個無約束的優化問題。

Max f(x,y)=2x22y2 (2)

s.t. x+y≥1

最優解: 在點(0,0),f(x,y) 取得最優解2。

這意味著如果約束是活躍狀態（下文），極值發生在▽f和▽g平行的點（α≥0）。 如果它們在極值上不平行，則意味著約束處於非活動狀態。

3. 互補鬆弛條件

α×g(x*)=0

這個條件是說，KKT乘子（對偶變量）或不等式約束(g(x*)≤0)在極值處為零。 我們可以將任何不等式約束分為兩類：1、活躍約束2、非活躍約束。

1）活躍約束：極值發生在約束的限制區域（邊界）上。 例如：問題1（見式1）最優解在

(x*=22,y*=13) ，約束 g(x*,y*)1=0。

2）非活躍約束：極值發生在可行區域內（不在限制區域的邊界上）。例如：問題2（見式2）最優解在

(x*=0,y*=0) ，約束g(x*,y*)1≥0。

從例1中可以看出▽f和▽g平行，α取正值。 在示例2中，我們看到α取負值的情況，導致約束變為非活躍狀態。 這意味著

Max f(x)+αg(x)=Max f(x)

只有當α取值為零時，上述情況才有可能。

所以g(x)≠0在極值點處，約束處於非活躍狀態

相關焦點

  • 深入理解拉格朗日乘子法和KKT條件
    （上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當面講好理解一些，註：下圖來自wiki）。而KKT條件是滿足強對偶條件的優化問題的必要條件，可以這樣理解：我們要求min f(x), L(a, b, x) = f(x) + a*g(x) + b*h(x)，a>=0，我們可以把f(x)寫為：max_{a,b}
  • 【直觀詳解】拉格朗日乘法和KKT條件
    【閱讀時間】8min - 10mun【內容簡介】直觀的解讀了什麼是拉格朗日乘子法，以及如何求解拉格朗日方程，並且給出幾個直觀的例子，針對不等式約束解讀了KKT條件的必要條件和充分條件拉格朗日乘法（Lagrange multiplier）是一種在最優化的問題中尋找多元函數在其變量受到一個或多個條件的相等約束時的求局部極值的方法。
  • 一挑三 FJ vs KKT
    以至於KT條件在10年後才重命名為KKT條件。 進一步理解雅克比矩陣的含義如下：如何理解Complementary Slackness？Summary.pdfhttps://www.math.uh.edu/~rohop/fall_06/Chapter3.pdfhttps://ocw.mit.edu/courses/mechanical-engineering/2-854-introduction-to-manufacturing-systems-fall-2010/lecture-notes/MIT2_854F10_kkt_ex.pdf
  • 如何直觀地理解條件隨機場,並通過PyTorch簡單地實現
    條件隨機場是一種無向圖模型，且相對於深度網絡有非常多的優勢，因此現在很多研究者結合條件隨機場（CRF）與深度網絡獲得更魯棒和可解釋的模型。本文結合 PyTorch 從基本的概率定義到模型實現直觀地介紹了 CRF 的基本概念，有助於讀者進一步理解完整理論。
  • 旋轉,複數最直觀的理解
    原標題：旋轉，複數最直觀的理解 上方超級數學建模可加關注 傳播數學乾貨，學會理性的方式去思考問題 複數的物理意義是什麼？ 我想 複數最直觀的理解就是旋轉！ 4*i*i = -4 就是「4」在數軸上旋轉了180度。 那麼4*i就是旋轉了90度。
  • 支持向量機(三):圖解KKT條件和拉格朗日乘子法
    前言支持向量機求解最優化參數的過程中需要用到拉格朗日乘子法和KKT條件，本文用清晰易懂的圖解法說明拉格朗日乘子法和
  • 科普欄目|將加子轉換為乘子--直觀理解e^πi+1=0
    x^n+…在對待e^πi這個數時，我們也可以不通過定義的無限項加和式來理解它，而是將其當作加子轉換為乘子的過程。其實在二維的複數平面上加子乘子動作的變換也是可以應用的。每個複數都是複平面上的一個點。對於加子，我們可以滑動平面，讓0點平移到此複數對應的點。而對於乘子，我們仍可以保持0點不動，將1變換到複數對應的點。
  • 用直觀的方法理解抽象的概念——線性相關(線性代數)
    線性代數教科書簡直就是一本充滿各種術語的字典，這些術語晦澀難懂，難以理解。學生們在考試前，只有幾個月的時間來理解特徵值，特徵向量，厄米特矩等。令人沮喪的是，老師通常不會在課堂上教矩陣的空間感、或者解釋方程的深刻含義。相反，他們只是讓你死記硬背解題方法，最終通過錯誤學習方法得到正確的答案，線性代數最終竟然被說成了是「文科」，背就可以了。
  • 波粒二象性:無法像理解宏觀規律的那樣直觀的「理解」波粒二象性!
    於是無論你怎麼去理解「水波/聲波」是一種粒子，或者「小球」以波的方式反射衍射，都是理解不了的。這不是智商的問題，是思維的問題。從波粒二象性的角度理解一個微觀事物（為了避免語意造成的理解偏差，不稱其為微觀粒子），無非是：1，該事物是一個獨立的單元，許多該事物構成的群體並非是連續的。2，許多該事物組成的群體表現出衍射，幹涉等特性。
  • 用直觀的方法理解抽象的概念——擴張空間(線性代數)
    為了直觀地解釋擴張空間，我將給你一個類比，就像我解釋線性相關一樣。這是用色彩組合來解釋線性代數概念的第二部分。第一部分是關於線性相關的，你可以在這裡讀到用直觀的方法理解抽象的概念——線性相關（線性代數）。紅色和黃色的跨度想像你是一個畫家，面前有一張空白畫布的。我遞給你一把畫筆和紅色和黃色兩兩種顏料。你能畫出的所有可能的顏色是什麼？
  • 數學中最具爭議的領域之一——混沌理論,通過雙擺直觀理解
    我們將不考慮流存在條件的細節。我們稍後會需要，周期軌道的定義，所以最好在這裡定義。點x軌道的集合是：{(x), 對於任意時間t} 。也就是說，對於某個t值，流將以循環方式返回到初始條件，並將永遠重複這個循環。例如，地球繞著太陽轉（忽略那些細節），地球將會繞回它的起點。我們可以對離散時間系統進行類似的討論。
  • 條件概率,全概率,貝葉斯公式理解
    有人試圖將「置信度」的直觀概念進行形式化的定義和應用。最普通的應用是基於打賭:置信度反映在行為主體願意在命題上下注的意願上。當信任有程度的時候，概率計算的定理測量信任的理性程度，就像一階邏輯的定理測量信任的理性程度一樣。很多人將置信度視為經典的真值（真或假）的一種擴展。Harold Jeffreys, Richard T.
  • 看看這個乘子法與KKT條件大招
    在介紹拉格朗日乘子法之前，先簡要的介紹一些前置知識,然後就拉格朗日乘子法談一下自己的理解。　　1.梯度　　梯度是一個與方向導數有關的概念，它是一個向量。如果滿足Slater條件，即原問題和對偶問題滿足強對偶性，則x*和λ*、μ*分別為原問題和對偶問題的最優解的充要條件是x0和λ0、μ0滿足下面的條件:
  • 究竟什麼才是數學新課標中的「幾何直觀」
    新課標給出的定義是：藉助幾何直觀和空間想像感知事物的形態與變化，利用空間形式特別是圖形，理解和解決數學問題的素養。其具體涉及：利用空間形式認識事物的位置關係、形態變化與運動規律；利用圖形描述、分析數學問題；建立形和數的聯繫；構建數學問題的直觀模型，摸索解決問題的思路。從直觀想像的定義來看，該素養主要包括兩個方面：幾何直觀和空間想像。
  • 乾貨| 直觀理解GAN背後的原理:以人臉圖像生成為例
    直觀上說，當辨別器中的一些隱藏神經元看到比如眼睛，嘴巴，頭髮等物體時，他們就會被激活。這些特徵對之後的其他任務比如分類是很有用的。如何訓練我們共同訓練生成器和辨別器，讓他們變得強壯，通過反覆訓練防止其中一個網絡比另一個網絡強大太多。為什麼輪迴訓練網絡使雙方共同變強而不是單獨訓練讓他們的性能更強大？
  • 圖解物理:40張動圖帶你直觀理解高中物理最難的「電磁場」
    圖解物理：40張動圖帶你直觀理解高中物理最難的「電磁場」
  • 看得見的高斯過程:這是一份直觀的入門解讀
    本文作者用幾個互動圖生動地講解了高斯過程的相關知識，可以讓讀者直觀地了解高斯過程的工作原理以及如何使其適配不同類型的數據。你可以通過文中的互動圖，以及上手感受具體的例子來理解這些知識。它們有助於解釋每個組件的影響，並展示高斯過程的靈活性。希望你在閱讀本文之後，對高斯過程的工作原理以及如何把它適配給不同類型的數據能有一個直觀的理解。
  • 40張動圖帶你直觀理解電磁場
    40個動圖，教你直觀的體會什麼是電磁場。
  • 對機械能守恆條件的深入理解
    二、課本對機械能守恆條件的表述        在只有重力或彈力做功的物體系統內，動能和勢能可以相互轉化，而總的機械能保持不變。        這個表述裡，機械能守恆的條件是「只有重力或彈力做功」。        上述問題中，卻有水平恆力和地面摩擦力做功，顯然不符合機械能守恆的條件。這似乎支持大多數老師的意見。
  • 12張動圖讓你理解深奧的機械原理,真的很直觀!
    【機械cax360第291期】機械原理是研究機械中機構的結構和運動，以及機器的結構、受力、質量和運動，這次我們通過直觀的動圖來理解機械的工作原理。▲蝸輪蝸杆結構蝸輪蝸杆機構常用來傳遞兩交錯軸之間的運動和動力。