凸规划对偶算法

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的拉格朗日乘子！