拉格朗日乘子法 KKT条件
目錄
1. 拉格朗日乘子法用于最優化的原因
2. 最優化問題三種情況
2.1 無約束條件
2.2 等式約束條件：拉格朗日乘子法
2.3 不等式約束條件：KKT
3. Lagrange對偶函數
3.1?對偶函數與原問題的關系
3.2 Lagrange對偶問題
（1）弱對偶性
（2）強對偶性
（3）KKT條件
? ? ? ? 在求解最優化問題中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法，即：
- 拉格朗日乘子法：在有等式約束時使用拉格朗日乘子法；
- KKT條件：在有不等約束時使用KKT條件。
1. 拉格朗日乘子法用于最優化的原因
? ? ? ?考慮一個簡單的問題目標函數f，等式約束，求解極小值點。
? ? ? ?f(x)在二維平面上畫出等高線就是一條條斜率相同的直線，h(x)=0在二維平面上畫出等高線就是一個圓，如下圖所示。可以明顯的看出，在圓圈h(x)的限制下，直線f(x)的最小值為-2，在左下角直線x1+x2=2和圓的交點上。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? （1）不考慮圓h(x)的限制時，f(x)要得到極小值，需要往f(x)的負梯度（下降最快的方向）方向走，如下左圖藍色箭頭。
? ? （2）考慮圓h(x)的限制時，要得到極小值，需要沿著圓的切線方向走，如下右圖紅色粗箭頭。注意這里的方向不是h(x)的梯度，而是正交于h(x)的梯度，h(x)梯度：右圖的紅色細箭頭。在極小值點，f(x)和h(x)的等高線是相切的。
? ? ??
? ? ? ?容易發現，在關鍵的極小值點處，f(x)的負梯度和h(x)的梯度在同一直線上，如下圖左下方critical point的藍色和紅色箭頭所示。注意圖中所示是同向的，但是這里并不一定是同向，有可能反向（因為等式約束h(x)=0，把h(x)變成-h(x)求解是一樣的，這個時候h(x)的梯度就相反了）。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? 由此可知，在極小值點，h(x)和f(x)的梯度在同一線上，有
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? 所以，對于f(x)和h(x)而言，只要滿足上面這個式子，同時使得h，解得的x就是我們要求的極小值點（或極大值點，為了簡單起見我們只討論極小值點）
? ? ? ? 要做到這一點，可以構造一個拉格朗日函數，對函數令偏導等于0求解，恰好等價于“滿足上面這個式子，同時使得h(x) = 0"，原問題轉化為對拉格朗日函數求極值問題，這就是拉格朗日乘子法，如下圖所示（注意一下這個μ的正負變化）。
? ? ? ? ? ? ? ? ? ? ? ? ? ?
參考：拉格朗日乘子法和KKT條件
2. 最優化問題三種情況
? ? 我們這里提到的最優化問題通常是指對于給定的某一函數，求其在指定作用域上的全局最小值（因為最小值與最大值可以很容易轉化，即最大值問題可以轉化成最小值問題）。提到KKT條件一般會附帶的提一下拉格朗日乘子。對學過高等數學的人來說比較拉格朗日乘子應該會有些印象。二者均是求解最優化問題的方法，不同之處在于應用的情形不同，KKT條件是對拉格朗日乘子法的一種泛化。
? ? ? 一般情況下，最優化問題會碰到一下三種情況：
2.1 無約束條件
這是最簡單的情況，解決方法通常是函數對變量求導，令求導函數等于0的點可能是極值點。將結果帶回原函數進行驗證即可。
2.2 等式約束條件：拉格朗日乘子法
? ? ? 設目標函數為f(x)，約束條件為h_k(x)，形如:
? ? ? s.t. 表示subject to ，“受限于”的意思，表示有個約束條件。
? ? ? ? ? ? ? ?
則解決方法是消元法或者拉格朗日法。消元法比較簡單不在贅述，這里主要講拉格朗日法，因為后面提到的KKT條件是對拉格朗日乘子法的一種泛化。
??? ? ? ?拉格朗日乘子法的求解流程大概包括以下幾個步驟：?
? 1）構造拉格朗日函數?
? 2）解變量的偏導方程?
? 3）代入目標函數即可?
? 關鍵在于構造拉格朗日函數，后面求解實際上就是高數里面基本的求偏導數的問題了。我們不妨另： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
然后分別對每一個變量求導，得出來的解代入目標函數就ok了！
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
例如：求這個橢球的內接長方體的最大體積
? ? ? ? 在條件
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ?下，求
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ?最大值。
? ? ? ?這個問題實際上就是條件極值問題，即在條件（1）?下，求的最大值。
當然這個問題實際可以先根據條件消去 z?(消元法)，然后帶入轉化為無條件極值問題來處理。但是有時候這樣做很困難，甚至是做不到的，這時候就需要用拉格朗日乘數法了。??
?首先定義拉格朗日函數F(x)：
? （?其中λk是各個約束條件的待定系數。） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? 然后解變量的偏導方程：
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ......,
如果有個約束條件，就應該有+1個方程。求出的方程組的解就可能是最優化值（高等數學中提到的極值），將結果帶回原方程驗證就可得到解。
回到上面的題目，通過拉格朗日乘數法將問題轉化為
?????
對求偏導得到
? ? ? ?
聯立前面三個方程得到和，帶入第四個方程解之
? ? ??
帶入解得最大體積為：
??????
?
2.3 不等式約束條件：KKT
? ? ? ?設目標函數f(x)，不等式約束為g(x)，有的教程還會添加上等式約束條件h(x)。此時的約束優化問題描述如下：
? ? ? ? 則我們定義不等式約束下的拉格朗日函數L，即廣義拉格朗日函數：
? ? ?其中，、是拉格朗日乘子，f(x)是原目標函數，hj(x)是第j個等式約束條件，λj是對應的約束系數，gk是不等式約束，uk是對應的約束系數。
常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數全部寫為一個式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，
KKT條件是說最優值必須滿足以下條件：
（1）?? ? ? ?原約束
（2）?
（3）?
求取這些等式之后就能得到候選最優值。其中第三個式子非常有趣，因為g(x)<=0，如果要滿足這個等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質的來源，如支持向量的概念。
基于KKT條件，不等式約束條件的問題基本也就解決了，下面來說說我自己的一點心得吧！?
第一點：拉格朗日乘子法求解優化問題是很有效的方法，對于限制條件比較多的情況下，特別是限制條件較為復雜的情況下，利用該方法可以很容易的求解出來。?
第二點：約束條件其實就是限定了問題的解決范圍，學會如何轉化和考量限制條件是解決問題的關鍵。?
第三點：基礎知識的重要性，比如說高數如果學不好的話。
3. Lagrange對偶函數
? ? ? ?在約束優化問題中，常常用拉格朗日對偶性來將原始問題轉為對偶問題，通過解對偶問題的解來得到原始問題的解。
3.1 為什么要利用對偶？
首先要明確，對偶問題的解不一定直接等于原問題的解（弱對偶），但是，對偶問題有兩點性質。
? ? ? （1） 滿足某些條件時，對偶問題直接等于原問題的解（強對偶）
? ? ? （2）無論原始問題是否是凸的，對偶問題都是凸優化問題
顯然，在某些情況下，直接對對偶問題求解可以得到原問題的解，而且對偶問題是凸優化，易于求解。所以利用對偶來求解是很有用的。
3.2?對偶函數與原問題的關系
（1）原始問題：
? ? ? ?假設f(x),ci(x),hj(x)是定義在Rn上的聯系可微函數，考慮約束條件下最優化問題：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
稱此約束最優化問題為原問題。
（2）廣義拉格朗日函數
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
（3）Lagrange對偶函數：
? ? ? ?定義拉格朗日對偶函數或者對偶函數g為拉格朗日函數關于x取得的最小值，即對α、β，有：
?? ? ? ? ? ? ? ? ? ?
通俗理解就是每確定一組(α，β)，就要找到一個x使得L最小，不同的(α，β)對應不同的g函數值。
（4）對偶函數與原問題的關系：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? 所以對偶函數是原問題的最優值下界，雖然不等式成立，但是如果α<0，并且讓α趨近于負無窮，這個時候g(α,β)=-∞，雖然也滿足不等式，但是此時沒有任何意義。所以只有當α≥0，這個時候g(α,β)＞-∞時，對偶函數才能給出原目標函數一個非平凡有意義的下界，稱此條件下的(α,β)是對偶可行的。圖示如下：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? 在圖中，實線——代表的是目標函數f(x)，虛線——代表的是約束條件c(x)，彩色的點線——代表λ取不同值的時候對應的拉格朗日函數L。我們可以看到，在約束條件可行(c(x)≤0)的區間內，拉格朗日函數都是小于目標函數的。在可行區間內，目標函數的最值將在x = -0.46處取得p?=1.54。
為什么對偶函數一定是凹函數呢？
? ? ? ?其實L可以理解為一個以固定x帶入c(x)和h(x)作為常數值系數，α、β作為變量的仿射函數。所謂仿射函數，就是f(x)=a*x+b形式，其實就是線性函數了。
? ? ? ?所以，g(α,β)為很多個仿射函數的逐個x取值點取最小值：
? ? ? ? ? ? ? ? ? ? ? ? L=Aα+Bβ+C? ? ??其中：A=c(x)? ? B=h(x)? ? C=f(x)
? ? ? 例如：L=2α+3β+1，L=α+2β+4，?L=5α+β+3等等。
便于理解，先不考慮β，這樣大致展示的圖像就是如下：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ?里面的每一條直線，都是以某一固定x作為系數，α作為變量的線性函數的直線，也就是當x固定時候，隨著α的變化，L的值不斷發生變化。
? ? ? ?當我們沿著L所在軸豎著切下來的時候，也就是圖中個藍色線，這個時候其實就是α固定，而對應不同的x情況下，L值的一個變化范圍。由圖可知，紅色線就是每次固定α，而找到一個x，使得L最小的走勢線，也就是g(α,β)的函數曲線，如下圖：
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ?凹折線就是g(α,β)的曲線，水平虛線就是原問題的最優函數值P*。由此可知，無論原問題和約束條件是什么樣的，對偶函數都是凹函數，且都小于等于原問題最優值。
3.3 Lagrange對偶問題
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ?對于任意一組(α，β)，其中α≥0，拉格朗日對偶函數給出了原問題的最優值的一個下界，因此，我們可以得到和參數α、β相關的一個下界。一個自然問題是：從Lagrange函數能得到的最好下界是什么？可以將這個問題表述為優化問題：
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
上述問題就稱之為Lagrange對偶問題。
? ? ? ? 前面講只有當α≥0，g(α,β)＞-∞時此時才有意義，滿足這樣一組條件的(α，β)是上述對偶問題的一個可行解。如果一個解（α*，β*)是上述對偶問題的最優解，則稱解(α*，β*)是對偶最優解或者最優Lagrange乘子。
此時對偶問題是一個凸優化問題，這是因為極大化目標函數是一個凹函數，且約束集合是一個凸集。
（1）弱對偶性
? ? ? ?Lagrange對偶問題的最優值，我們用*表示，根據定義，這是通過Lagrange函數得到的原問題最優值*的最好下界。特別地，我們有下面簡單但是非常重要的不等式
? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
即使原問題不是凸問題，上述不等式也成立，這個性質稱為弱對偶性。
（2）強對偶性
? ? ? ? 與弱對偶性相對應的有一個強對偶性（strong duality）?，強對偶即滿足：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ?強對偶是一個非常好的性質，因為在強對偶成立的情況下，可以通過求解對偶問題來得到原始問題的解，在 SVM 中就是這樣做的。當然并不是所有的對偶問題都滿足強對偶性 ，在 SVM 中是直接假定了強對偶性的成立，其實只要滿足一些條件，強對偶性是成立的，比如說?Slater 條件與KKT條件。
（3）KKT條件
? ? ? ?假設x*是原始問題的最優解，α*和β*是對偶問題的最優解。如果強對偶成立，那么原問題最優解和對偶問題最優解必須滿足KKT條件，屬于充分必要條件。
?? ? ? ? ? ? ? ? ??
?
參考：
拉格朗日對偶理解：https://www.cnblogs.com/gczr/p/10521551.html
總結
以上是生活随笔為你收集整理的拉格朗日乘子法 KKT条件的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数学基础：高斯分布
- 下一篇： 决策树（Decision Tree）和随