如何通俗地講解對偶問題？尤其是拉格朗日對偶lagrangian duality？

01-05

能不能給我講講對偶問題，kkt條件？為什麼存在duality gap？滿足kkt條件又能說明什麼？
我們能不能在知乎上開個optimization workshop，這樣應該比live要強。

我先邀請了幾位專業人士，希望你們能不吝賜教。先謝謝了。也請大家幫忙多邀請人來回答。
我的提問也都是拋磚引玉，任何關於優化的理解，都可以寫下來，我不勝感激了。我相信很多知乎上的朋友，都會從你們的答案中得到幫助，謝謝了。

謝謝題主 @孤雲獨去閑邀請。前段時間就看到這個問題了，現在看到很多答主都答得不錯，那我給一個基於column geometry（翻譯成列幾何？）的解釋吧。拉格朗日對偶有很多種理解和推導的方式，這一種是我比較喜歡的，幾何和代數的方法結合，也比較有intuition。關於KKT條件的幾何解釋很多答主都提了，那個也是比較經典的，我這個回答就先不涉及了。

我們考慮優化問題如下，記作問題（P）。（知乎編輯器似乎出了點問題，函數括弧圓括弧顯示不了，我就用方括弧了）

$z^* = min_x f[x]$ $ext{s.t. } g_i[x]leq 0 ,~forall~ i=1,ldots,m,$ $xin X$

大家都知道（P）的拉格朗日對偶問題（D）寫作

$v^* = max_{ugeq 0} min_{xin X} underbrace{f[x]+u^T g[x]}_{L[x,u]}$

其中的函數L[x,u]就是我們熟知的拉格朗日函數。

這邊先給一個小note，實際上原問題和拉格朗日對偶的代數形式就是一組max-min關係式（只有max和min的順序換一下）。具體說明如下。

引理：(P)也可以寫成 $z^* = min_{xin X}max_{ugeq 0}L[x,u]$ .

證明是很容易的，留作練習。那麼這裡其實我們看到所謂的拉格朗日對偶從代數上看很簡單，就是研究這一對max-min優化問題之間的關係。

好了，之前都是預熱。接下來我們來看如何通過column geometry來理解這對關係式。這一段首先介紹一些符號和定義。首先注意到給定一個 $xin X$ ,實際上(P)可以用一個在 $mathbb{R}^{m+1}$ 里的向量來描述：

$left[s,z ight]=[s_1,s_2,ldots,s_m,z]=[g_1[x],g_2[x],ldots,g_m[x],f[x]]=[g[x],f[x]]$ .

這樣我們把問題轉換到 $[s,z]$ 定義的空間上，定義集合

$I:={ [s,z]in mathbb{R}^{m+1}: exists xin X ext{ s.t. } sgeq g[x], zgeq f[x] }$ .

然後我們引入「支撐」（support）的概念，我們稱一個超平面 $H_{u,alpha}:= { [s,z]in mathbb{R}^{m+1}:u^Ts+z=alpha }$ 是 $I$ 的下支撐（lower support）僅當

$u^Ts+zgeq alpha, forall~ [s,z]in I.$

直觀的意思就是指 $H_{u,alpha}$ 在 $I$ 的下方。下面給一張圖片加以解釋（黃色部分就是 $I$ ，那條線就代表超平面 $H_{u,alpha}$ ）。

注意到這裡我們圖上看到 $I$ 畫的是一個凸集（convex set），我們指出在凸優化的一般情況下這是一個必然的事實。

引理：如果 $X$ 是凸集， $f,g_1,ldots,g_m$ 都是 $X$ 上定義的凸函數，那麼 $I$ 是一個凸集。

證明也很容易，利用凸函數epigraph的性質就能立即得出，這裡從略。

好了，準備工作到這裡，我們給出對偶問題（D）的column geometry解釋：拉格朗日對偶問題（D），在空間 $[s,z]$ 中的幾何含義是：找到 $I$ 的下支撐超平面 $H_{u,alpha}$ 中與z軸交點最「高」（即 $alpha$ 最大）的那個超平面。注意到在 $m=1$ 的情況下（ $[s,z]$ 是二維的）我們可以知道 $-u$ 是直線 $H_{u,alpha}$ 的斜率， $alpha$ 則是截距。這個intuition到高維情況也是成立的。

把上面提到的幾何含義用代數表示出來則是：

$max_{u,alpha} ~ alpha$ $ext{s.t. } ~ u^Ts+zgeq alpha, ~ forall~ [s,z]in I$

注意到我們其實只需要考慮 $ugeq 0$ 的情況，因為如果 $u$ 存在一個coordinate是負的，那麼我們總可以找到一個無限大的 $s$ （注意 $I$ 的定義，這樣的 $s$ 永遠是存在的）使得 $u^Ts+z<alpha$ ，所以以上問題也等於

$max_{ugeq 0,alpha}~alpha$ $ext{s.t.} u^Ts+zgeq alpha,~ forall~ [s,z]in I$

= $max_{ugeq 0,alpha}~alpha$

$ext{s.t. } underbrace{u^Tg[x]+f[x]}_{L[x,u]}geq alpha,~forall~xin X$

= $max_{ugeq 0,alpha } alpha$

$ext{s.t. } min_{xin X} L[x,u]geq alpha$

= $max_{ugeq 0}min_{xin X}L[x,u]$

我們於是發現這就是問題（D）。

這就是拉格朗日對偶基於column geometry的幾何解釋。順便說一下，如果我們考慮一個更特殊的情況， $f,g$ 都是線性函數，即線性規劃問題，column geometry會給出更多很有意思的幾何解釋，這邊就留給感興趣的同學自己去琢磨了。

--------------------------------------------------------------------------------------------------------------------------

我的另一個相關回答：（討論更抽象的對偶優化問題，不過核心思路都是一致的，對偶的核心思想就是要找原問題的線性majorization）

線性空間的對偶空間和優化里的拉格朗日對偶有什麼關係？ - 知乎

拋磚引玉, 說一下(Lagrangian) duality是怎麼來的。先考慮下面的nonlinear programming:

$min {f(mathbf{x}): g_i(mathbf{x})leq 0,; i=1,2,...,m}$ (1)

現在的問題是如何找到問題(1) 的最優值的一個最好的下界? 首先我們知道若方程組

$egin{align}f(mathbf{x})<v\g_i(mathbf{x})leq 0, i=1,2,...,mend{align}$ (2)

無解，則 $v$ 是問題(1)的一個下界。注意到方程組(2)有解可以推出對於任意的 $m{lambda}geq mathbf{0}$ , 以下方程

$f(mathbf{x})+sum_{i=1}^{m}lambda_ig_i(mathbf{x})<v$ (3)

有解。因此根據逆否命題，方程組(2)無解的充分條件是存在 $m{lambda}geq mathbf{0}$ ，讓方程(3)無解。方程(3)無解的充要條件是

$min_{mathbf{x}} f(mathbf{x})+sum_{i=1}^m lambda_ig_i(mathbf{x})geq v$ (4)

因為我們要找最好的下界，所以這個時候的 $v$ 和 $m{lambda}$ 應該取

$v=max_{m{lambda}geq mathbf{0}}min_{mathbf{x}} f(mathbf{x})+sum_{i=1}^{m}lambda_ig_i(mathbf{x})$ (5)

由此引入了dual problem. 證明邏輯是根據式(5)取 $v$ 和 $m{lambda}$ , 則(4)成立，從而導出(3)無解，然後可以知道(2)無解，因此 $v$ 是問題(1)的下界

最近也在看關於優化的東西，題主在問題補充里問了好多，我暫且以二維空間 $R^2$ 舉例，從簡單的無約束的優化（0梯度條件），到等式約束優化(拉格朗日條件)，再到不等式約束優化（KKT條件），寫點對於優化問題自己能寫的理解，權當做拋磚引玉。

1. 無約束的優化問題

$min f(x)$

其中， $x=(x_1,x_2)$

注意我在圖裡畫了等高線。此時 $f(x)$ 在局部極小值點 $x^*=(x_1^*,x_2^*)$ 處的梯度必然為0，比較容易理解。這個梯度為零的條件是局部極小值點的必要條件。這樣，優化問題的求解變成了對該必要條件解方程組。

2.帶等式約束的優化問題

$minf(x)$ ,

s.t.

$h(x)=0$ .

與無約束的問題不同。我們所要求的極小值點被限制在曲線 $h(x)=0$ 上，我們將 ${x|h(x)=0}$ 稱為可行域, 解只能在這個可行域里取。如下圖所示，曲線 $h(x)=0$ （黑色實曲線）經過無約束極小值點（黑點）附近。那麼滿足約束的極小值點應該與黑點儘可能近。我們將 $f(x)$ 的等高線不斷放大，直到與曲線 $h(x)=0$ 相切，切點即為所求。相切是關鍵，是極小值點的必要條件。

把 $h(x)=0$ 沿著曲線方向參數化為 $x(t)$ , $x^*=x(t^*)$ 。必有 $f(x)$ 在紅點 $x^*$ 的梯度方向與 $x(t)$ 的切線方向垂直，即

$abla f(x^*) cdot dot x(t^*)=0$

另外，由於 $h(x)=0$ 為常數，那麼也有複合函數 $h(x(t))=0$ , 因此 $h(x(t))$ 在 t 的導數必為0，根據鏈式法則有

$abla h(x) cdot dot x(t)=0$ （內積為0，說明 $abla h(x^*)$ 與 $dot x(t^*)$ 垂直）

因為 $abla f(x^*)$ 垂直於 $dot{x}(t^*)$ ， $abla h(x^*)$ 垂直於 $dot{x}(t^*)$ ，所以 $abla f(x^*)$ 與 $abla h(x^*)$ 共線，有 $abla f(x^*)+lambda abla h(x^*)=0$

$x^*$ 若為最小值點就必須滿足上式和問題中的約束 $h(x^*)=0$ ,這個必要條件就叫作拉格朗日條件，為了好記，定義一個拉格朗日函數

$L(x, lambda)=f(x)+lambda h(x)$

令其偏導為0，正好就得到拉格朗日條件。

如此，帶等式約束的優化問題轉化為了無約束的優化問題，只需要對拉格朗日條件解方程組即可。這裡λ就是拉格朗日乘子，有多少個等式約束就有多少個拉格朗日乘子。

3. 帶不等式約束的優化問題

$min f(x)$ ,

s.t.

$h(x) leq 0$ .

當只有一個不等式起作用時, 如我們把問題2里的等式約束 $h(x)=0$ 改為 $h(x) leq 0$ ，如下圖所示，可行域變成了陰影部分，最小值點還是切點，情況和問題2完全一樣，只需要把不等號當做等號去求解即可。

當兩個不等式起作用時，那麼問題就來了

$min f(x)$ ,

s.t.

$g_1(x) leq 0$ ,

$g_2(x) leq 0$ .

如下圖，當 $f(x)$ 的等高線慢慢擴大時，等高線與可行域(陰影部分)第一次相遇的點是個頂點，2個不等式同時起作用了。滿足約束的最小值點從原來的黑點位置(切點)移動到了紅點位置，現在跟哪條約束函數曲線都不相切。這時候就需要用到kkt條件了。這裡的「條件」是指：某一個點它如果是最小值點的話，就必須滿足這個條件（在含不等式約束的優化問題里）。這是個必要條件，前面說的也全部是必要條件。

這個問題的解 $x^*$ 應滿足的KKT（卡羅需-庫恩-塔克）條件為：

1. $mu_1 geq 0$ ， $mu_2 geq 0$ ;

2. $abla f(x^*)+mu_1 abla g_1(x^*)+mu_2 abla g_2(x^*)=0$ ;

3. $mu_1g_1(x^*)+mu_2g_2(x^*)=0$ .

其中，μ叫KKT乘子，有多少個不等式約束就有多少個KKT乘子。加上問題3中的約束部分，就是完整版的KKT條件。對於有等式的情況，你把其中一個不等式約束換成等式，可行域變成了半條曲線，最小值點還是那個紅點，和下面這種情況是一樣的。

下面看看KKT條件是怎麼來的。在問題2中我們知道了約束曲線的梯度方向與曲線垂直，我在上圖畫出了兩條約束曲線的負梯度方向（綠色箭頭）和等高線的梯度方向（紅色箭頭）。如果這個頂點是滿足約束的最小值點，那麼該點處（紅點），紅色箭頭一定在兩個綠色箭頭之間( $- abla g(x)$ 方向一定指向 $g(x)$ 減小的方向，即 $g(x)<0$ 的那一邊)。即 $abla f(x^*)$ 能被 $- abla g_1(x^*)$ 和 $- abla g_2(x^*)$ 線性表出（ $abla f(x^*)= -mu_1 abla g_1(x^*) -mu_2 abla g_2(x^*)$ ），且係數必非負（ $mu_1 geq 0$ ， $mu_2 geq 0$ ）。也就是kkt條件中的1和2

1. $mu_1 geq 0$ ， $mu_2 geq 0$ ;

2. $abla f(x^*)+mu_1 abla g_1(x^*)+mu_2 abla g_2(x^*)=0$ .

有時候，有的不等式約束實際上不起作用，如下面這個優化問題

$min f(x)$ ,

s.t.

$g_1(x) leq 0$ ;

$g_2(x) leq 0$ ;

$g_3(x) leq 0$ .

如下圖的 $g_3(x_1,x_2) leq 0$ 是不起作用的

對於最小值點 $x^*$ ,三個不等式約束的不同在於

$g_1(x^*)=0$ （起作用）

$g_2(x^*)=0$ （起作用）

$g_3(x^*)<0$ （不起作用, 最小值點不在 $g_3(x)=0$ 上）

這時，這個問題的KKT條件1，2成了：

1. $mu_1 geq 0$ ， $mu_2 geq 0$ ， $mu_3 geq 0$ ;

2. $abla f(x^*)+mu_1 abla g_1(x^*)+mu_2 abla g_2(x^*)+mu_3 abla g_3(x^*)=0$ .

條件2中的 $mu_3 abla g_3(x^*)$ 這一項讓我們很苦惱啊， $g_3(x^*)$ 的綠色箭頭跟我們的紅色箭頭沒關係。要是能令 $mu_3 = 0$ 就好了。加上條件3：

3. $mu_1g_1(x^*)+mu_2g_2(x^*)+mu_3g_3(x^*)=0$

恰好能使 $mu_3=0$ 。由於 $g_1(x^*)=0$ ， $g_2(x^*)=0$ ，所以前兩項等於0，第三項 $g_3(x^*)<0$ , 在條件3的作用下使得 $mu_3=0$ . 正好滿足需求。如果再多幾項不起作用的不等式約束，比如 $g_4(x) leq 0$ 。要使

$mu_1g_1(x^*)+mu_2g_2(x^*)+mu_3g_3(x^*)+mu_4g_4(x^*)=0$

就只能有 $mu_3g_3(x^*)+mu_4g_4(x^*)=0$

同樣地， $g_3(x^*)<0$ , $g_4(x^*)<0$ , 只能出現 $mu_3=mu_4=0$ 或者 $mu_3$ 和 $mu_4$ 異號的情況。但注意條件1限制了 $mu_3 geq 0$ ， $mu_4 geq 0$ ，所以只能有 $mu_3=mu_4=0$ 。因此不管加了幾個不起作用的不等式約束，條件2都能完美實現：目標函數 $f(x)$ 的梯度 $abla f(x)$ 被起作用的不等式約束函數 $g(x)$ 的負梯度（ $- abla g(x)$ ）線性表出且係數 $mu$ 全部非負（紅色箭頭被綠色箭頭夾在中間）。這樣，優化問題的求解就變成對所有KKT條件解方程組。

如果再定義一個拉格朗日函數

$L(x, mu)=f(x)+mu_1 g_1(x)+mu_2 g_2(x)+...$

令它對x的偏導為0，就是KKT條件中的條件2了。

最後說明一下，以上所有都是局部極小值點的必要條件。據此求得的解不一定是局部極小值點（更別提全局了），原因是上圖中我所畫的等高線也許根本就不閉合，也就是說我們一直想要靠近的等高線中間的黑點壓根就是個鞍點或者近似鞍點！

------------------------2017.6.6--------------------------

順帶一提，李航老師《統計學習方法》第一版105頁式(7.27)中的第1，2行就是這裡的KKT條件2（我這裡把偏置b算在x里了），第3行是KKT條件3，第4行是問題中的不等式約束，第5行是KKT條件1。

這裡筆者用博弈論裡面的直觀結論解釋問題，拋磚引玉。

1. 構造Lagrangian：

對於下面的優化問題，

$egin{split} min_{x}f(x) \ s.t. quad g(x)leqslant0 enspace and enspace exists g(x)<0 \ x in mathbb{R}^{n}, enspace g(x) in mathbb{R}^{m} end{split}$

我們構造一個新問題，

$egin{split} min_{x in mathbb{R}^{n}} max_{lambda in mathbb{R}^{m}}mathcal{L}(x,lambda) = f(x)+{lambda}^{T}g(x) \ s.t. quad lambda in mathbb{R}^m geqslant0 \ x in mathbb{R}^{n}, enspace g(x) in mathbb{R}^{m} end{split}$

非常易證，這個問題等同於原問題。那我們把它叫做primal problem。

2. 博弈論中的重要結論：

2.1 同時我們有Min-Max 不等式

$sup_{y in Y} inf_{x in X}f(x,y) leqslant inf_{x in X} sup_{y in Y}f(x,y)$

2.2 和Minimax Theroem：當 $f(x,y)$ 對 $x$ 為凸函數， $-f(x,y)$ 對 $y$ 為凸函數（即對 $y$ 凹謝謝 @又紅又正指正）時候，上述不等式取得等號。

2.3 下面我來解釋一下這兩個結論：

不等式：如果 $f(x,y)$ 是一個零和遊戲中的payoff函數， $x$ 目的是減小此函數值（函數值對他來說是成本）， $y$ 想要增大此函數值（函數值對他來說是利潤），則上述不等式中左邊為 $y$ 的「保底利潤」（最壞情況下，他也一定至少能獲得這麼多利潤），右邊為 $x$ 的「保底損失」（最壞情況下他損失也就這麼多）。那麼顯而易見，上述不等式成立，不然與「保底」的概念矛盾。

Minimax定理：即說明了此函數存在saddle point，博弈雙方有了一個納什均衡（誰也無法單方面地獲得好處）。

3. 定義dual problem：

定義dual problem： $max_{lambda in mathbb{R}^{m}} min_{x in mathbb{R}^{n}}mathcal{L}(x,lambda) = max_{lambda in mathbb{R}^{m}} min_{x in mathbb{R}^{n}}f(x)+lambda^{T}g(x)$

由2.中的結論， $mathcal{L}(x,lambda)$ 天然對 $lambda$ 凹，那麼只要 $f(x)$ 與 $g(x)$ 對 $x$ 凸，那麼 $mathcal{L}(x,lambda)$ 就對 $x$ 凸對 $lambda$ 凹，於是等式成立。這個結論即是convex problem最顯著最重要的特點。

如果等式不成立，那麼差值就叫dual gap。

希望能幫助到您。

Dual problem 跟primal problem 可以看成本來是兩個問題，因為優化的順序不同而會得出兩個不一定相關的值（但是 $mathop{min}_{x}mathop{max}_{y}f(x,y) geq mathop{max}_{y}mathop{max}_{x}f(x,y)$ 還是成立的，直觀理解的話高中經常用的二次函數就可以了）。

兩者的差值就是duality gap，描述了我用另一種方式刻畫問題的時候所造成的誤差，強對偶的情況下最優值沒有差別。

在最優點處將會滿足KKT 條件，但是KKT條件本身並不需要問題滿足強對偶。

關於KKT條件什麼時候不滿足，有一種另外的理解是他要求各個函數的梯度張成足夠大的空間（因為KKT的最後一條本質上是一個Ax=0的問題），希望有助於理解。

建議題主閱讀Boyd Convex Optimization Chap. 5.5

換一個問題來看對偶問題吧

大家知道變分問題吧

把極小化函數變成極小化一個泛函 $int L(dot x,x)dx$

然後可以寫出來他的最優性條件就是Euler－Lagrange方程

$-frac{d}{ds}(D_qL(dot x(s),x(s))+D_xL(dot x(s),x(s)))=0$

我們儘可能把他化成一個Hamilton ODE（Hamilton－Jacobi方程的特徵線）

這裡我們要構造一個函數

$H(p,x):=pcdot q(p,x)-L(q(p,x),x)$

這裡suppose $p(s):=D_qL(dot x(s),x(s))$

於是對於H我們有hamliton ODE寫出來就是E－L方程了

奇妙的是這裡的H 和L 就是凸優化里的對偶的關係

L=H*,H=L*

具體可以看evans

還有一個很好的幾何解釋

過兩天有空我來寫寫在

《凸優化理論》［MIT那本啊］這本書里詳細介紹了

最近還是有很多pde和優化關係的文章的都很不錯

Yu Mao, Bin Dong and Stanley Osher, A nonlinear PDE-based method for sparse deconvolution, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8(3), 965-976, 2010.

A variational perspective on accelerated methods in optimization. A. Wibisono, A. Wilson, and M. I. Jordan. Proceedings of the National Academy of Sciences, 133, E7351-E7358, 2016. [ArXiv version]

W. Su, S. Boyd and E. J. Candès. A differential equation for modeling Nesterov"s accelerated gradient method: theory and insights. Journal of Machine Learning Research 17(153), 1--43. (This is the long form or journal version of the NIPS paper.) (pdf)

Pratik Chaudhari, Adam Oberman, Stanley Osher, Stefano Soatto, and Guillame Carlier, Deep Relaxation: Partial Differential Equations for Optimizing Deep Neural Networks, April 2017

我提了workshop的想法，我自己不寫點什麼實在是有點偷懶。不過我很不擅長優化，我的背景更多是統計，概率，分布的那些東西。

在Andrew Ng 教授講解支持向量機（svm）的那篇教案（note）里，他講過svm的primal和dual的形式，我覺得是我見過的最好的svm教案。下面是鏈接：

教案

http://cs229.stanford.edu/notes/cs229-notes3.pdf

視頻

http://m.open.163.com/movie?plid=M6SGF6VB4rid=M6SGJVMC6

請一定要看英文的那個版本，有個中文的，比較淺，沒談到duality。

一些粗淺的個人理解：有時候求原始問題是複雜的，尤其當原始問題是一個nonconvex problem時，這個時候我們便把原始問題轉化為它的對偶問題。

相比直接計算原始問題，求解對偶問題會為我們的計算帶來相當的便利，比如樓主提到的SVM引入對偶形式便是一個很好的例子。

求出對偶問題的解至少能為原始問題找到一個下界（Weak duality always holds），如果運氣好的話（滿足KKT），此時求出的便是原始問題的最優解。

最近也在研究支持向量機，這學期也正在學最優化理論，上周剛剛總結了一下KKT條件並寫了一篇分享，算是一個拋磚引玉吧~

淺談最優化問題的KKT條件 https://zhuanlan.zhihu.com/p/26514613

最近再看線性規劃，涉及到對偶，恰好前段時間在學習SVM機的時候也有對偶理論，兩者對照起來學習，感覺稍微有點融會貫通了。

自身學在習的時候一直力求直觀易於理解，能夠透過數學公式看透背後的原理，希望寫出來也能通俗易懂。

線性規劃中的對偶理論：

原問題： $maxquad c^{T}x\ s.t. Axleq b,xgeq 0$

對偶問題：

$minquad b^{T}y\A^{T}ygeq c,ygeq 0$ 其中，A,b,c,x,y均為向量。

用拉格朗日數乘法把原問題轉換成無約束問題： $L(x,lambda)=c^{T}x+lambda^{T}(b-Ax)\ 其中lambda>0,即lambda的每個元素都大於0，維數和b的維數相等，即約束條件個數\因為(b-Ax)geq 0恆成立，且lambda geq0,\令z=minlimits_lambda L(x,lambda)\則有：z=minlimits_{lambda}L(x,lambda)=c^{T}x,此時lambda=0\ 於是，原問題等價於:\maxlimits_xz=maxlimits_xminlimits_lambda L(x,lambda)$ 好了，重點來了，所謂對偶就是把max和min的順序換一下，

$對偶問題的表述如下：\minlimits_lambda maxlimits_xL(x,lambda)\注意下標！\ 接下來證明為什麼可以由對偶問題解出原問題，這是最關鍵的一步，也是最精彩的地方\-----------------\ 令g(lambda)=maxlimits_xL(x,lambda),\由於g(lambda)的表達形式中lambda未作限制，因此與原問題相比，少了一個約束條件，\因此,g(lambda)geq max c^{T}x\ 從另一方便看，lambda(b-Ax)始終大於等於0，也可以證明g(lambda)geq max c^{T}x成立，\ 上式說明g(lambda)是原問題的上界\ 求得原問題的上界有什麼用呢\ 我們一步步往下推，\假設s=max c^{T}x,我們的目的就是要求出s值。\ 在上一步中我們看到，g(lambda)geq s,去不同的lambda值就能得到一系列的g值，\其中有的g(lambda)比s大很多，\有的比s大的不多，\甚至可能和s一樣大。\ 我們去和s值最接近的g(lambda)值作為s值的近似，\於是通過求得g(lambda)中最接近s的值作為原問題的解。\ 那麼在一系列的g(lambda)中，到底哪一個最接近s呢？\ 前面已經證明了g(|lambda)是s的上界，\那麼g(lambda)中的最小值就是最接近s的上界了，\寫成數學公式如下即為\minlimits_lambda g(lambda)=minlimits_lambdamaxlimits_xL(x,lambda)\ 這就是原問題的對偶表示，\至此，已經說明了為什麼對偶問題的解可以作為原問題的解（近似解）\ 下面，討論等式g(lambda)geq s中何時等號成立\ 當等號成立時，\對偶問題的解就是原問題的精確解，\即可以找到一個lambda，使得g(lambda)=s,這種情況就叫強對偶\ 當等號不成立時，\對偶問題的解和原問題的解總存在一定偏差，\只是原問題解的一個近似，這種情況叫弱對偶\ \$ 第一次用Tex，排版不是很熟練，蛋疼ing。。。

我們把最原始的s表示成了max,min的形式，好了，現在需要做的工作就是把min,max形式的對偶問題反退回s那種形式，即從 $minlimits_lambdamaxlimits_xL(x,lambda)\這種形式反推回\ minquad b^{T}y\quad quad s,tquad A^{T}ygeq c,ygeq0\這種形式$ 其實只是意思是一樣的，只是表達方式不一樣。 $s^{$ 令 $lambda^{T}=y,x^{T}=eta$ 代入可得