凸規劃對偶演算法

A. 運籌學基礎的目錄

前言/I
第1部分 預 備 知 識
第1章 預備知識/3
1.1 向量3
1.1.1 向量定義及線性運算3
1.1.2 向量的線性相關性4
1.1.3 向量組的秩6
1.2 矩陣7
1.2.1 矩陣的概念與運算7
1.2.2 矩陣的求逆運算9
1.2.3 矩陣的初等變換11
1.2.4 矩陣的分塊12
1.2.5 矩陣的秩16
1.3 二次型及其正定性19
1.3.1 二次型及其矩陣表達式19
1.3.2 二次型的正定性21
1.4 多元函數的導數與極值23
1.4.1 一元函數的導數、極值與泰勒公式23
1.4.2 多元函數的梯度、黑塞矩陣與泰勒公式27
1.4.3 多元函數的極值34
習題137
第2部分 線 性 規 劃
第2章 線性規劃的基本概念/43
2.1 線性規劃問題及其數學模型43
2.1.1 問題的提出43
2.1.2 線性規劃問題的數學模型45
2.2 兩個變數問題的圖解法45
2.3 線性規劃數學模型的標准形式及解的概念49
2.3.1 標准形式49
2.3.2 將非標准形式化為標准形式50
2.3.3 有關解的概念51
2.4 線性規劃的基本理論54
2.4.1 凸集與凸組合54
2.4.2 線性規劃基本定理56
習題261
第3章 單純形法/63
3.1 單純形法原理63
3.1.1 單純形法的基本思路63
3.1.2 確定初始基本可行解67
3.1.3 最優性檢驗69
3.1.4 基變換71
3.1.5 無窮多個最優解及無界解的判定74
3.2 單純形表75
3.3 人工變數及其處理方法81
3.3.1 大?M?法82
3.3.2 兩階段法84
3.3.3 關於退化與循環的問題87
3.4 改進單純形法88
3.4.1 單純形法的矩陣描述88
?*3.4.2 改進單純形法91
習題396
第4章 線性規劃的對偶理論/101
4.1 線性規劃的對偶問題101
4.1.1 對偶問題的實例101
4.1.2 三種形式的對偶關系103
4.2 對偶理論109
4.3 對偶解(影子價格)的經濟解釋116
4.4 對偶單純形法117
4.5 靈敏度分析122
習題4133
第5章 運輸問題/137
5.1 運輸問題的數學模型及其特點137
5.1.1 產銷平衡運輸問題的數學模型137
5.1.2 運輸問題數學模型的特點139
5.2 表上作業法141
5.2.1 確定初始基本可行解141
5.2.2 位勢法求檢驗數145
5.2.3 用閉迴路法調整當前基本可行解148
5.2.4 表上作業法計算中的兩個問題154
?*5.3 表上作業法的理論解釋157
5.3.1 用西北角規則求得的解是基本可行解158
5.3.2 對於非基格存在唯一閉迴路161
5.3.3 檢驗數σ?ij與v?n=a的取值無關162
5.4 產銷不平衡的運輸問題165
習題5170
第6章 線性規劃應用實例/174
6.1 套裁下料問題174
6.2 配料問題175
6.3 生產工藝優化問題177
6.4 有配套約束的資源優化問題178
6.5 多周期動態生產計劃問題180
6.6 投資問題181
6.6.1 投資項目組合選擇182
6.6.2 連續投資問題182
?*6.7 運輸問題的擴展184
習題6189
第7章 整數規劃/195
7.1 分枝定界法197
7.2 割平面法204
7.3 0-1型整數規劃209
7.3.1 特殊約束的處理210
7.3.2 0-1型整數規劃的典型應用問題211
7.3.3 求解小規模0-1規劃問題的隱枚舉法214
7.4 指派問題與匈牙利解法216
7.4.1 指派問題的數學模型216
7.4.2 匈牙利法的基本原理217
7.4.3 匈牙利法求解步驟219
習題7227
第8章 目標規劃/231
8.1 線性目標規劃的基本概念與數學模型231
8.2 線性目標規劃的圖解法235
8.3 線性目標規劃的序貫式演算法239
8.4 線性目標規劃的單純形演算法245
習題8249
第3部分 非線性規劃
第9章 非線性規劃的基本概念與基本原理/255
9.1 非線性規劃的數學模型255
9.1.1 非線性規劃問題舉例255
9.1.2 非線性規劃問題的一般數學模型257
9.1.3 局部最優解與全局最優解259
9.2 無約束問題的最優性條件260
9.3 凸函數與凸規劃265
9.3.1 凸函數定義與性質265
9.3.2 凸函數的判別准則269
9.3.3 凸規劃273
9.4 解非線性規劃的基本思路275
?*9.5 有關收斂速度問題279
習題9280
第10章 一維搜索/281
10.1 黃金分割法282
10.1.1 單谷函數及其性質282
10.1.2 0.618法基本原理與步驟283
10.2 加步探索法288
10.2.1 基本原理和步驟288
10.2.2 計算舉例289
10.3 牛頓法290
?*10.4 拋物線法292
習題10294
第11章 無約束問題的最優化方法/295
11.1 變數輪換法295
11.2 最速下降法298
11.2.1 基本原理298
11.2.2 最速下降法的演算法步驟300
11.3 牛頓法302
11.3.1 牛頓方向和牛頓法302
11.3.2 計算舉例304
11.3.3 修正牛頓法306
11.4 共軛梯度法307
11.4.1 共軛方向與共軛方向法308
11.4.2 正定二次函數的共軛梯度法311
11.4.3 非二次函數的共軛梯度法317
習題11318
第12章 約束問題的最優化方法/320
12.1 約束極值問題的最優性條件320
12.1.1 起作用約束與可行下降方向320
12.1.2 庫恩-塔克條件323
12.2 可行方向法328
12.2.1 基本原理與演算法步驟329
12.2.2 計算舉例330
12.3 近似規劃法334
12.3.1 線性近似規劃的構成334
12.3.2 近似規劃法的演算法步驟335
12.3.3 計算舉例335
12.4 制約函數法339
12.4.1 外點法339
12.4.2 內點法343
習題12347
第4部分 動 態 規 劃
第13章 動態規劃/351
13.1 動態規劃問題實例351
13.2 動態規劃的基本概念353
13.2.1 多階段決策過程353
13.2.2 動態規劃的基本概念355
13.3 最優性定理與基本方程358
13.3.1 最優性原理358
13.3.2 最優性定理359
13.3.3 動態規劃的基本方程360
13.4 動態規劃應用舉例365
13.4.1 資源分配問題366
13.4.2 生產與庫存計劃問題371
?*13.4.3 設備更新問題378
習題13382
*第5部分 決 策 分 析
*第14章 決策分析/387
14.1 決策的基本概念387
14.1.1 決策問題實例387
14.1.2 決策問題中的主要概念388
14.1.3 決策問題的分類389
14.2 確定型決策390
14.3 風險型決策391
14.3.1 最優期望益損值決策准則391
14.3.2 決策表法392
14.3.3 決策樹法394
14.4 效用理論398
14.4.1 效用的概念與效用曲線400
14.4.2 效用曲線的類型404
14.4.3 最大效用期望值決策准則及其應用405
14.5 不確定型決策408
習題14411
第6部分 優化軟體計算實例
第15章 優化軟體計算實例/417
15.1 MATLAB 7.0優化工具箱計算實例417
15.2 LINDO/LINGO軟體計算實例429
習題答案及提示/445
參考文獻/489
索引/490

B. 「對偶」是什麼意思

用兩個結構相同、字數相等、意義對稱的片語或句子來表達相反、相似或相關意思的一種修辭方式叫對偶。

C. 最大熵原理的理論方法

這是一個約束極值問題，通過Lagrange乘數法可以求得其最優解，從熵作為系統不確定性的度量的角度來看，等可能系統的不確定性是最大的，這一結果與我們的直觀是一致的。更進一步，許多問題都附帶一些實際的限制，也可以理解為在解決問題之前，我們可以獲得一些已知信息。由此，(1)可以深化為
為各階統計矩函數,，表示實際觀測到的各階統計矩的期望值。這里由於為一正常數，為簡便記，取。同(1),仍然可以利用Lagrange乘數法來求解。做Lagrange函數:
解出最優解。但當較大時，往往計算困難。姜昱汐提出了一個解決此問題的方法[5]。利用對偶規劃理論，可得問題(2)的求解相當於求解:
其中，(3)是凸規劃(2)的對偶規劃，優勢在於(3)是一個變數個數較(2)少的無約束規劃，可以直接利用軟體求解。 對於連續系統，記為一連續隨機變數，概率密度函數為。此系統的熵定義為[6]。在一些條件的約束下，使得系統熵最大的問題一般有下面形式：
其中為一些約束，右端為觀測值。這是一個有
個約束的泛函極值問題。關於這一問題有如下定理。
定理2.1[7]若在條件約束下目標泛
使得滿足泛函，所給出的歐拉方程組
由此方程組可解出目標。

D. 是否為凸規劃max f(x)=-x1*x1-x2*x2+x3 sit :x3+x1<=0 ,x3+x2<=0.x1,x2,x3>=0，為什麼。可否用KKT求解

是凸優化問題，上述問題等價於minimum－x1－x2；st：x1＊x1＋x2＊x2＆lt；＝9－x2＆lt；＝0，三者全部都是凸函數。如果只想求得答案，直接畫圖即可406如果想用凸優化的方法0628由於原問題滿足強對偶性q求對偶問題就可解得也可以用KKT條件求解406

E. 求解二重向量叉乘中拉格朗日公式的詳細推導過程

支持向量機的原理很簡單，就是VC維理論和最小化結構風險。在閱讀相關論文的時候，發現很多文章都語焉不詳，就連《A Tutorial on Support Vector Machines for Pattern Recognition》這篇文章對拉格朗日條件極值問題的對偶變換都只是一筆帶過，讓很多人覺得很困惑。下面我將就SVM對線性可分的情況作詳盡的推導。

如上圖所示，有一堆訓練數據的正負樣本，標記為：，假設有一個超平面H：，可以把這些樣本正確無誤地分割開來，同時存在兩個平行於H的超平面H1和H2：

使離H最近的正負樣本剛好分別落在H1和H2上，這樣的樣本就是支持向量。那麼其他所有的訓練樣本都將位於H1和H2之外，也就是滿足如下約束：

寫成統一的式子就是：

（1）

而超平面H1和H2的距離可知為：

SVM的任務就是尋找這樣一個超平面H把樣本無誤地分割成兩部分，並且使H1和H2的距離最大。要找到這樣的超平面，只需最大化間隔Margin，也就是最小化。於是可以構造如下的條件極值問題：
（2）

對於不等式約束的條件極值問題，可以用拉格朗日方法求解。而拉格朗日方程的構造規則是：用約束方程乘以非負的拉格朗日系數，然後再從目標函數中減去。於是得到拉格朗日方程如下：

（3）

其中：
（4）

那麼我們要處理的規劃問題就變為：
（5）

上式才是嚴格的不等式約束的拉格朗日條件極值的表達式。對於這一步的變換，很多文章都沒有多做表述，或者理解有偏差，從而影響了讀者後續的推演。在此我將詳細地一步步推導，以解困惑。
（5）式是一個凸規劃問題，其意義是先對α求偏導，令其等於0消掉α，然後再對w和b求L的最小值。要直接求解（5）式是有難度的，通過消去拉格朗日系數來化簡方程，對我們的問題無濟於事。所幸這個問題可以通過拉格朗日對偶問題來解決，為此我們把（5）式做一個等價變換：

上式即為對偶變換，這樣就把這個凸規劃問題轉換成了對偶問題：
（6）

其意義是：原凸規劃問題可以轉化為先對w和b求偏導，令其等於0消掉w和b，然後再對α求L的最大值。下面我們就來求解（6）式，為此我們先計算w和b的偏導數。由（3）式有：

（7）

為了讓L在w和b上取到最小值，令（7）式的兩個偏導數分別為0，於是得到：
（8）

將（8）代回（3）式，可得：

（9）

再把（9）代入（6）式有：

F. 什麼是凸二次規劃

二次規劃（Quadratic programming），在運籌學當中，是一種特殊類型的最佳化問題。

[編輯] 簡介二次規劃問題可以以下形式來描述：

f(x) = (1 / 2)xTQx + cTx
受到一個或更多如下型式的限制條件：

Ex = d
vT 是 v 的轉置。

如果Q是半正定矩陣，那麼f(x)是一個凸函數。如果有至少一個向量x滿足約束而且f(x)在可行域有下界，二次規劃問題就有一個全局最小值x。 如果Q是正定矩陣，那麼全局最小值就是唯一的。如果Q=0，二次規劃問題就變成線性規劃問題。

根據優化理論，一個點x 成為全局最小值的必要條件是滿足 Karush-Kuhn-Tucker(KKT)條件。當f(x)是凸函數時，KKT條件也是充分條件。

當二次規劃問題只有等式約束時，二次規劃可以用線性方程求解。否則的話，常用的二次規劃解法有：內點法(interior point)、active set和共軛梯度法等。凸集二次規劃問題是凸優化問題的一個特例。

[編輯] 對偶每個二次規劃問題的對偶問題也是二次規劃問題。我們以正定矩陣Q為例：

L(x,λ) = (1 / 2)xTQx + λT(Ax − b) + cTx
對偶問題g(λ)，可定義為

我們可用 : 得到L的極小

x * = − Q − 1(ATλ + c),
對偶函數：

g(λ) = − (1 / 2)λTAQ − 1ATλ − cTQ − 1ATλ − bTλ
對偶問題為：

maximize : − (1 / 2)λTAQ − 1ATλ − (ctQ − 1AT + bT)λ

subject to :

計算復雜性當Q正定時，用橢圓法可在多項式時間內解二次規劃問題。當Q負定時，二次規劃問題是NP困難的(NP-Hard)。即使Q 存在一個負特徵值時，二次規劃問題就是NP困難的。

G. 跪求解答最優化方法問題，判定是否為凸規劃 max f(x)=x1+x2 sit :x1*x1+x2*x2<=9 ,x2>=0.急求解題過程

是凸優化問題，
上述問題等價於minimum -x1-x2 ；st ：x1*x1+x2*x2<=9 ，-x2<=0，三者全部都是凸函數。
如果只想求得答案，直接畫圖即可。如果想用凸優化的方法，由於原問題滿足強對偶性，求對偶問題就可解得，也可以用KKT條件求解。

H. 求解原始問題和對偶問題常用的優化演算法有哪些

1. 支持向量機的目的是什麼？
對於用於分類的支持向量機來說，給定一個包含正例和反例（正樣本點和負樣本點）的樣本集合，支持向量機的目的是尋找一個超平面來對樣本進行分割，把樣本中的正例和反例用超平面分開，但是不是簡單地分看，其原則是使正例和反例之間的間隔最大。
超平面是什麼呢？簡單地說，超平面就是平面中的直線在高維空間中的推廣。那麼，對於三維空間，超平面就是平面了。對於更高維的空間，我們只能用公式來表達，而缺少直觀的圖形了。總之，在n維空間中的超平面是n-1維的。
超平面的公式為。公式中的w為可以調整的系數向量，b為bias。注意我們的表達習慣，所有的向量都是列向量，所以在第一項的內積中向量w需要進行轉置。
現在考慮樣本集合{xi，di}，xi是輸入的特徵，di是樣本對應的分類。現在規定當樣本xi屬於第一類時，di為1，當xi屬於第二類時，di為-1。
那麼，線性可分的意思就是一個超平面可以把兩類樣本完全地分割開來。用公式表達就是：

你現在可能會問，那麼如果不是線性可分的情況應該怎麼辦呢？事實是這些會在後面處理到。在這里我們首先討論線性可分的情況，然後將其拓展到線性不可分的情況.
現在假設對於線性可分的樣本集，我們有了一個分割超平面，現在我們想通過調整w0和b0讓它分割的正樣本和負樣本保持最大的間隔，這樣我們就獲得了最優的超平面。實際上在操作過程中，我們最大化的是離超平面最近的點到超平面的距離。也就是說，我們要讓超平面盡量遠離最近的點。從圖中可見超平面到正樣本最近點的距離和超平面到負樣本最近點的距離是相等的。這是個巧合么？
假設我們已經找到了一個超平面，它離正樣本最近點的距離大於離負樣本最近點的距離，那麼這個離超平面最近的點就是負樣本中的最近點。而考慮到我們的目標，我們還會調整超平面的位置使它還可以增大一些，即使這樣會犧牲離正樣本最近點的距離。所以調整到最後的結果肯定是超平面離兩側最近點的距離是等距的。

為了更形象地表現正負樣本的間隔，我們可以在分割超平面的兩側再定義兩個超平面H1和H2（如圖中虛線所示），這兩個超平面分別通過正樣本和負樣本中離分割超平面最近的樣本點（圖中加了外圈）。從以上分析可以知道，超平面H1和H2離分割超平面是等距的。
我們定義超平面H1和H2上面的點叫做支持向量。正負樣本的間隔可以定義為超平面H1和H2之間的間隔，它是分割超平面距最近正樣本點距離和最近負樣本點距離之和。
從圖中可以看出，支持向量對於分割超平面的位置是起到關鍵作用的。在優化分割超平面位置之後，支持向量也顯露出來，而支持向量之後的樣本點則對分類並不關鍵。為什麼這樣說呢？因為即使把支持向量以外的樣本點全部刪除，再找到最優的分割超平面，這個超平面的位置跟原先的分割超平面的位置也是一樣的。總結起來就是：
支持向量包含著重構分割超平面所需要的全部信息！
2. 樣本點到超平面距離的表示
如何求一點到超平面的距離呢？
現在我們來看看系數向量w0是什麼含義？回憶一下，w0實際上是超平面的法向量！
那麼，對於任意一個樣本點x，它可以表示為：

其中xp是x在超平面上的投影，r是x到超平面的幾何距離（幾何間隔）。
設 ，
現在由定義有g(xp)為0，則有。
現在我們開看，g(x)實際上度量了樣本點x到超平面的距離，在||w0||恆定的情況下，g(x)絕對值的大小反映了幾何間隔r的大小。我們給g(x)起個名字叫做函數間隔。注意幾何間隔r和函數間隔g(x)都是有正負號的，代表著處於超平面的不同側。

3. 最大化間隔
我們已經知道了函數間隔和幾何間隔的表示，現在回到正題，我們需要最大化支持向量到分割超平面的距離，當然在最開始我們不知道哪些向量是支持向量。
我們的目的是最大化支持向量到分割超平面的幾何間隔r，而不是最大化函數間隔g(x)，為什麼呢？因為超平面方程的系數可以同比例增大或者減小，而不改變超平面本身。所以||w0||是不固定的，這就會影響函數間隔g(x)的大小。
所以我們需要最大化的是幾何間隔r，這等價於我們固定||w0||，然後最大化函數間隔g(x)。但是實際上我們不會這么做，通常的處理方法是固定函數間隔g(x)的絕對值為1，然後最小化||w0||。也就是說我們把支持向量到分割超平面的函數間隔g(x)的絕對值設定為1，然後最小化||w0||。

4. 正式的表述
現在我們可以正式地表述這個問題了。我們需要最小化||w0||，也就是最小化超平面權重向量w0的歐幾里得范數。但是有沒有限定條件呢？還記得上一節最後一句話么？
「也就是說我們把支持向量到分割超平面的函數間隔g(x)設定為1，然後最小化||w0||」
所以最小化||w0||是有限定條件的，如何表述限制條件呢？我們把支持向量對應的g(x)定為+1或者-1（取決於支持向量處於分割超平面的哪一側，也就是說是正樣本還是負樣本），也就表明了對於所有的正樣本點來說，g(x)是>=+1的，而對於負樣本來說，g(x)是<=-1的。
回想g(x)的定義：
，
我們可以把限制條件寫下來：

現在我們可以把上面的問題寫的更簡練：
目標函數：

限制：

1/2是為了以後計算方便所加的，N是樣本點的個數。
現在我們的第一個任務結束了，我們把要尋找最優的分割超平面的問題轉化為帶有一系列不等式約束的優化問題。這個最優化問題被稱作原問題。我們不會直接解它，而是把它轉化為對偶問題進行解決。至於如何將其轉化為對偶問題，這是以後幾節的內容。
等式約束極小的最優性條件
對支持向量機的求解都是將上節說的原問題轉化為對偶問題進行求解的，這些內容都是最優化課程中的內容。
回憶上節的內容，我們的目標是尋找函數在若干約束條件下的最小值。在上節的原問題中，約束條件是包含不等式的，本節先考慮簡單的問題，即考慮只包含等式約束的最優化問題：
（1）
其中f(x)被稱作目標函數，而下面是一系列的等式約束。回想一下，當沒有任何約束存在的時候，應該怎樣尋找最優點呢？事實上x*是最優點的必要條件是：

而如果函數f(x)是凸函數的話，這個條件也是充分條件。
插入一個說明，如果函數f(x)是一個實值函數，x是一個n維向量，那麼f(x)對向量x的導數被定義為：

回到目前的問題，當我們尋找約束存在時的最優點的時候，約束的存在雖然減小了需要搜尋的范圍，但是卻使問題變得更加復雜。為了使問題變得易於處理，我們的方法是把目標函數和約束全部融入一個新的函數，即拉格朗日函數，再通過這個函數來尋找最優點。
為了形象化地分析這個問題，我們考慮目標函數是三變數的函數並且只有一個約束的情況：
（2）
從幾何上來看，上面的問題（2）就是從曲面上來尋找函數的最小值。假設問題（2）的最優解是。我們現在做曲面Ω上任一條通過點x的光滑曲線l：（由於曲線l是在曲面Ω上的，所以自然有）。
令最優點對應的t為t*。因為x*是曲面Ω上的最優點，所以x*也是曲線l上的最優點，所以t*是一元函數的最優點，所以在這一點它的導數是0。通過鏈式法則我們得到：

這個式子說明了在x*這一點，函數的梯度向量 和曲線l在x*處的切線是垂直的。由於曲線l是任意的，所以梯度向量和曲面Ω是垂直的。
回憶高等數學的結論，的方向就是曲面Ω的法線方向，所以和必然在同一直線的方向上，所以必定存在一個常數μ*，有。
我們可以把它寫成更加精煉的形式。如果我們構造二元函數，上面的結論就可以表達為必定存在著常數μ*，使。
我們把構造的函數稱作拉格朗日函數，而其中的μ稱作拉格朗日乘子。

關於只有等式約束的拉格朗日函數的引入，也可以參考維基網路中的兩個變數函數的例子。
以上是一個特殊情形的分析，並且只包含了一個約束。那麼包含等式約束的一般情況，也就是問題（1）來說，我們同樣可以構造拉格朗日函數，不過由於包括多個等式約束，表達稍微不同：
。
也就是說，每一個等式約束都對應著一個拉格朗日乘子。那麼x*是最優點的必要條件就是，存在相應的拉格朗日乘子μ*，使得以下兩個式子成立：
（實際上就是原問題（1）的約束條件換了種寫法）
這兩個式子就是最優點的必要條件，當然如果函數是凸函數的話，這兩個式子也是充分條件。
現在我們的目標達到了，也就是把目標函數和一系列的等值約束融合到了一個函數（拉格朗日函數）裡面，這樣只需要解（3）和（4）這兩個式子就可以找到最優點，其優點是不言而喻的。而在下一節中我們將會討論包含不等式約束的最優化問題。
尋找最優值的下界
我們首先要引入包含不等式約束的優化問題，標准形式如下：
（1）
f(x)是目標函數，而後面分別是一系列的不等式約束和等式約束。
我們首先明確幾個概念：
可行點（可行解）：所有滿足約束的點x。
可行域：所有可行點組成的點集，記為R。正式寫出來就是：

最優點（最優解）：滿足約束（也就是處於可行域之內）並且使目標函數達到最小的點，記為x*。
最優值：如果找到了x*，p* = f(x*) 就是最優值。
明確了這些概念以後我們就接著說下面的內容了。
與上節所說的只包含等式約束的情況類似，我們定義拉格朗日函數如下：

我們來看看，這與上節的拉格朗日函數有什麼不同？多了一系列的不等式約束對應的項，所以也多了一系列的拉格朗日乘子。在這里需要強調的是，所有的λi必須是大於等於0的（也即是不等式約束對應的乘子要求大於等於0，我們記為λ≥0，意思是每個都λi≥0）。至於為什麼要這樣要求，後面自然可以看出來。
接下來我們定義一個重要的函數，我們定義拉格郎日對偶函數（the Lagrange al function）如下：
（2）
所以拉格朗日對偶函數就是把看成x的函數所找到的最小值。找到這個最小值有什麼意義呢？
我們先把結論寫下來，這個結論十分重要，是本節論述的目的：
對偶函數產生了原問題（1）最優值p*的一個下界，也就是說，對於任意的λ≥0和任意的μ來說，有：
（3）
那麼如何證明（3）呢？
這個證明步驟十分簡潔。假設x*是原問題（1）中的最優解，也就是f(x*) = p*。

最後兩行的推導是考慮到x*是在可行域R內的，所以肯定有，當然前提是λ≥0，這也就是為什麼在一開始要做這個規定的原因了。
我們如何理解這個不等式（3）呢？下面給出兩個直觀的解釋：
解釋一：線性逼近的解釋

我們首先重寫問題（1），就是把問題（1）換個更加緊湊的方式來表達，首先我們定義示性函數：

同樣我們也可以定義另外一個示性函數：

有了這兩個示性函數的幫助，現在我們可以把問題（1）重新寫成一個沒有約束的形式：
（4）
我們來看看這個優化問題（4）和問題（1）是等價的么？我們可以把（4）的後面兩大項看做是對違反約束條件的x的懲罰函數。起的作用是對違反不等式約束的x進行「無限的」懲罰，也就一旦，懲罰就等於無窮大。而起的作用是對違反等式約束的x進行懲罰，一旦，懲罰就為無窮大。這樣對（4）中目標函數的優化跟對（1）中目標函數在約束條件下的優化就是同一回事，是不是？也就是說，（1）和（4）這兩個問題是等價的問題，但是在（4）中約束被融合到目標函數中來了。

現在我們再回頭看看（2），也就是拉格朗日對偶函數，它也是個優化問題，我們對比它所優化的函數和（4）中所優化的函數，把它們重寫在一起：
（2）中的目標函數
（4）中的目標函數
可見在問題（2）和問題（4）中，我們優化的目標函數區別在於懲罰項不同，（4）中的懲罰項是無限的，就是說一旦違反約束，就施加無窮大的懲罰；而在（2）中我們的懲罰項是線性的，就是說隨著gi(x)和hi(x)的不同，懲罰項是線性變化的。所以（2）和（4）中需要優化的目標函數有很大的不同，用（2）來逼近（4）是很不準確的。但是我們可以看出，對於任意的u，任意的λ≥0和任意的μ來說都有：
（我們把λ限制為大於等於0了）
所以在任意點，（2）中的目標函數的值都是小於（4）中的目標函數的值，所以（2）中找到的最優值肯定是小於（4）中找到的最優值的。再結合前面說的（1）和（4）是等價的問題，所以不等式（3）是成立的。

解釋二：交換max和min的次序
我們首先可以看出：

為什麼會有這個結果呢？當x滿足約束的時候，也就是對所有的i來說有並且，如果我們想通過調整λ和μ讓變大怎麼辦呢？只有讓λ全部為0（注意λ只能大於等於0），這樣就消去了小於0的項，至於，無論μ怎麼變都是沒有影響的。所以當x屬於可行域的時候上式的結果是f(x)。如果x違反了約束呢？在做sup運算的時候只需要對滿足和的項對應的乘子定為+∞，而把其他的項對應的乘子設為0，就可以讓整個式子的結果變為無窮大。
所以我們可以看出來，在問題（1）中的帶約束的優化問題和直接優化是一回事，也就是說：

現在我們把inf和sup兩個運算符調換次序，顯然有：

我們重寫（2）式：
（2）
可以看出結論了，也就是λ≥0時（3）式成立：
（3）
好了，費了半天的勁我們說明了一個問題，就是不等式（3）是怎麼來的。
總結一下，不等式（3）用文字敘述就是：
如果我們把拉格朗日函數看做是x的函數，然後取下確界（注意：是在整個定義域里取下確界，而不是僅僅在可行域里取值，也就是說取下確界時對x是沒有約束的），那麼得到的結果就是原優化問題（1）的最優值的一個下界。

至於我們得到這個結果有什麼用，下節再說。
對偶問題
回憶上一節，對如下的原問題：
（1）
我們定義了拉格朗日對偶函數：

然後我們證明了：，其中p*是原問題的最優值。
也就是說我們找到了原問題最優值的一個下界。既然我們找到了一個下界，顯然我們要找到它最好的下界。什麼是最好的下界的？顯然就是所有下界當中最大的那一個。所以我們要把最大化，當然我們還要記得我們需要限制。我們把要優化的函數和約束條件正式寫下來就是：
（2）
與原問題（1）相對應，我們把上面的問題（2）稱作拉格朗日對偶問題（Lagrange al problem）。顯然，對偶問題的最優值d*就是我們可以獲得的p*的最優下界，也就是所有下界中離p*最近的一個，它們的關系是：
（3）
我們把這個不等式叫做弱對偶性質（Weak Duality）。
順其自然，我們可以引出一個重要的概念，對偶間隙，其定義為，用文字敘述就是原問題的最優值與通過拉個郎日對偶函數獲得的其最好（最大）的下界之差。由不等式（3）可以看出，對偶間隙肯定是大於等於0的。
那麼有沒有可能在某種情況下，對偶間隙消失了呢？也就是說對偶問題的最優值與原問題的最優值相等了呢？
我們將要敘述一下Slater條件：
Slater條件：
存在x滿足：
Slater條件即是說存在x，使不等式約束中的「小於等於號」要嚴格取到「小於號」。
可以證明，對於凸優化問題（關於凸優化問題，請參考維基網路），如果Slater條件滿足了，則：

這種情況稱為強對偶性質（Strong Duality）。
下面的問題是，如果對偶間隙消失了，會發生什麼有趣的現象呢？
如果對偶間隙消失了，也就是說，如果對偶問題存在著最優點λ*,μ*並且使其對應的最優值等於p*，這時會發生什麼情況呢？還記得上一節我們證明的過程么：
（4）
在對偶間隙消失的情況下，中間所有的不等號都要變成等號：
（5）
注意，（5）中的λ和μ都加了星號，表示它們是對偶問題的最優點。（5）中有兩個重要的等號，已經加了標記。
我們能得出什麼結論？
1 .我們先來看等號1：
它說明了原問題的最優點x*是使取得最小值的點。
2. 我們再來看等號2：
它說明了：

由於我們限制了每一個λi≥0，所以上式中每一項都是非正的。這樣我們又可以得出結論：
(6)
等式（6）被稱作是互補性條件，我們可以把它換種寫法：

或者寫成它的等價形式（逆否命題）：

也就是說，只要一個不為0，另一個就必為0！
互補性條件有著重要的意義。它說明了當時，x*是處於可行域的內部的，這時不等式約束並不起作用，此時；而的點肯定是可行域邊界的點（）。也就是說只有積極約束才有不為0的對偶變數。而這在支持向量機中有著重要的意義。回想在第一節我們最後的結論，支持向量機尋找最大間隔超平面可以歸結為一個優化問題：
目標函數：

限制：

那麼哪些不等式約束對應著不為0的對偶變數呢？顯然，只有當時，這個約束對應的對偶變數才可能不為0，而意味著什麼？意味著這個約束對應的樣本點xi是支持向量！也就是說：
只有支持向量才對應不為0的拉格朗日乘子！