上篇（第二十九篇）對拉格朗日對偶模型的剖析中，小白對關于拉格朗日乘子的理解還是滿意的，即拉格朗日乘子的本質在于描述對偶問題所關聯的對偶函數空間彼此膨脹（彼此約束）的數學建模。但是對"相加"（拉格朗日函數表示為問題函數和約束函數"相加"）的解釋不甚滿意。因此，本章内容首先會再次分析拉格朗日函數，得出"相加"的含義是問題函數和約束函數對偶關系的數學建模。接着，小白會引出凸優化，KKT條件以及強弱對偶，進而更完善的完成關于拉格朗日對偶模型的理解。

圖1

如圖1，對于函數Z=f(x,y)。可以理解為，f是一個面（x,y）到一個标量數軸Z的映射，每一個Z的取值h對應着平面（x,y）上一條線h=f(x,y)，這條線可理解為一維的空間。即，Z=f(x,y)把面（x,y）分割成了無數個h=f(x,y)空間，Z的變化對應着不同空間。

圖2

因此，如圖2，我們可以把問題函數f(x,y)和約束函數Q(x,y)看成是對平面(x,y)以不同映射方式分割而成的無數個函數空間。其中一個問題函數空間對應着問題的極值，其中一個約束函數空間對應着約束的邊界（Q(x,y)=0）。

小白感覺，從函數空間角度去理解似乎很好，很清晰。此刻，回到問題本身，我們的目标是對于"約束條件下的問題函數的極值"建模，即，在特定的約束函數空間邊界，問題函數空間的邊界在哪呢？

我們發現，問題函數空間和約束函數空間都在（x,y）的平面上，因此，我們隻需要朝着約束函數邊界的方向去尋找，找到和約束函數邊界相切的問題函數空間，切點（P0）的坐标就是我們問題的解，問題空間對應的Z的值就是我們要找的極值。

因此，我們理解，Q(x,y)和f(x,y)相加，背後的含義是問題的極值和約束邊界交合，一方的增加，另一方是必減少，此消彼長，對偶而生。相加是對 對偶關系的建模。

我們在此順便理解下拉格朗日乘子，其背後的含義是和約束函數空間邊界相切的問題函數空間伸縮度的度量，這個度量就是切點的斜率。

趁熱打鐵，我們再來理解下拉格朗日對偶函數L（x,y,a）。

如上是拉格朗日函數，先從約束函數開始，對于約束空間，體現為在平面（x,y）上的一條曲線，如下圖3中的黑色曲線。

圖3

然後，我們再想，這條曲線由經過f(x,y)的映射，變成了如圖3中的紅色的曲線。這個曲線就是L，這個曲線L在(x,y)上的投影是約束函數的函數空間，同時，這個曲線又由問題函數空間f（x,y）膨脹而成，因此，曲線L(即對偶模型函數)是問題函數和和約束函數的 雙重疊加。另外，拉格朗日乘子就是紅色曲線最高點的斜率。

圖4

如上圖4，約束條件可能是不等式。這時，約束空間由邊界曲線變成了有邊界的面。這種情況，我們不難分析 ，其等同于等式約束的情況。

圖5

如上圖5，假如不等式 約束函數是凸的，那麼可能出現如上情況。這種情況，我們不難分析，這時候約束是無效的，即，無約束的情況。

對于上面圖4和 圖5兩種情況 ，在拉格朗日對偶模型裡，通過KKT條件進行概括；

KKT條件

通常，我們擴展一個廣義的拉格朗日函數，同時包含等式約束和不等式約束的情況，如下：

對于的KKT條件是：

其中：

（1） 是拉格朗日函數解的條件；

（2） 被稱作松弛互補條件，其目的是覆蓋上面圖4和圖5的情況，即考慮到約束函數有效和無效的情況，比如beta為0，其實約束是無效的；

（3） 和（4）是原約束條件；

（5）拉格朗日乘數，即約定。度量邊界的膨脹率。

圖6

如圖6。我們可能會想到，約束函數空間邊界如上圖6中紅色曲線時，情況将會如何？我們知道實際的極值點可能是P0點，但我們可能找到了P1。這時，我們有一種直觀上的感受，就是約束邊界如何表現為向外凸起的形狀時，切點即為極值點的結論才是正确的，即在非凸的（Non-convex）情況下，我們找到的極值點，可能不是全局最優的。因此，拉格朗日對偶模型常會考慮問題函數和約束函數是凸集的一些場景，我們稱之為凸優化問題 。下面列出一些常用的凸優化拉格朗日對偶模型。

注：如果對偶模型遇到非凸函數時該如何處理呢，小白思考，我們應該可以嘗試把非凸問題轉化為凸問題，這樣就可以了。當然，下面還會談到弱對偶，是與非凸情況相關的。

"凸"的定義

首先，如下是凸集的定義：

如上定義2.1對于凸集的定義，很容易形象化的理解，即一個凸集的元素x和元素y之間連線上的任一元素都屬于當前的凸集。定義3.1是關于凸函數的定義。

線性凸優化模型

如上，線性凸優化模型。我們可以理解，線性凸優化模型的問題函數和約束函數都是凸的，其實它滿足2.1凸定義中的等式條件。

二次規劃模型

如上，二次規劃模型定義，即QP。我們看到，問題函數對于資源空間x是二次的，是凸函數（想象抛物線是凸的）；約束函數是線性函數，也是凸的。

二次約束二次規劃模型

如上，二次約束二次規劃模型，即QCQP。我們看到，問題函數和約束函數都是二次的，都是凸的。

半正定模型

如上是半正定模型，回顧小白《對矩陣的線性臆想》一文，tr表示矩陣的"迹"。半正定規劃也是凸的。

從字面上看，對偶必有兩者，意為問題函數和約束函數。一是從問題本身出發解決問題，二是，從約束出發解決問題。下面我們從約束函數的角度出發，來解決問題。從而得出與問題函數的強弱關聯。

如果我們直接求解問題函數，我們是求解L(x)的最大下确界（inf）

我們如果x看作常量 ，把拉格朗日乘子看作變量，如下：

下面我們僅考慮問題函數f(x,y)和僅有一個約束函數h(x,y)的情況。這樣我們隻考慮h(x,y)映射的Y和f(x,y)映射的Z的情況，如下圖，Y和Z形成了一個封閉的空間G：

圖7

如圖7，從（Z,y）的空間看，極值點就是Ｐ0處。而拉格朗日乘子就是P0處的切線的斜率。我們知道，對如上圖的凸區間G，拉格朗日乘子變化（即對偶問題自變量的變化），可形象的看作上圖中切線沿着閉區間的邊界運動，因此，一定是能和P0點重合的。因此，這就體現了從對偶的角度解決問題。

圖8

我們再考慮如上圖8的情況，（Z,y）的空間G非凸區間内。我們發現沿着G的邊界是永遠找不到最優的點（上方紅色的點），但是我們可以找到一個次優的點（下方紅色的點）。而我們稱此時，問題和對偶問題時弱對偶的，對偶問題的解和實際的解有差距，我們稱這個差距（紅色點之間的距離）稱為對偶間隔。

如下圖，我們再從解決問題函數角度看，可能是如下這種情況，即約束函數的非凸特點，造成了弱對偶。

圖9

因此，我們理解 ，非凸的問題函數或約束函數，可能是弱對偶的；凸優化是強對偶的。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!