最优化模型与算法-基于Python实现 课件 第3、4章 凸优化模型、对偶理论

凸优化模型最优化模型与算法——基于Python实现第三章01优化模型大部分优化模型可以表示为如下形式(3.1.1)该模型表示在所有满足及的中寻找函数的最小值。我们称为优化变量，称函数为目标函数，不等式称为不等式约束，相应的函数称为不等式约束函数。方程称为等式约束，相应的函数称为等式约束函数。如果没有约束(即)，我们称问题(3.1.1)为无约束优化问题。目标函数和所有约束函数有定义的点的集合，(3.1.2)称为优化问题(3.1.1)的定义域。当点且满足约束条件和时，称是可行点。3.1.1基本术语当问题(3.1.1)至少有一个可行点时，我们称该优化问题是可行的，否则称其是不可行的。所有可行点的集合称为可行集或约束集。问题(3.1.1)的最优值定义为(3.1.3)我们允许取值为。如果问题不可行，我们有(按惯例，空集的下确界为)。如果存在可行解满足：当时，，那么，此时我们称问题(3.1.1)无下界。如果可行且，我们称约束的第个不等式在处起作用。如果，则约束不起作用。如果去掉某个约束条件不改变可行集，我们称该约束是冗余的。3.1.1基本术语最优点与局部最优点如果

是可行的并且

，称

为最优解。所有最优解的集合称为最优解集，记为

(3.1.4)如果问题(3.1.1)存在最优解，我们称最优值是可达的，并称问题可解。如果

是空集，我们称最优值是不可达的。对于最优值不可达的情况，可以考虑

-次优解，即满足

(其中

)的可行解

。上述最优解，或

-次优解的概念是在整个可行域中考虑的。相对的，称可行解

为局部最优解，如果存在

使

(3.1.5)即

是下面关于

的优化问题的解

(3.1.6)直观上，这意味着点

使

在一点的邻域且在可行集内取到最小值。“全局最优”常被用来代替“最优”以区分“局部最优”和“最优”。在本书中，最优意味着全局最优。“”3.1.1基本术语一般地，可以采用变量变换的方法将优化问题进行变形，转化为与之等价的但更加易于求解的优化问题。变量变换例3.1.1考虑单项式函数的极小化问题，

，其中

表示

，

。该问题的目标函数通常不是凸函数，定义变量

，则

，

。这是一个凸函数。设

是一一映射，其值域包含原问题的定义域

，即

。定义函数

和

为

(3.1.7)考虑关于

的优化问题

(3.1.8)称标准形式问题(3.1.1)和问题(3.1.8)通过变量变换或变量代换

相联系。这两个问题明显等价：如果

是问题(3.1.1)的最优解，那么

是问题(3.1.8)的最优解；如果

是问题(3.1.8)的最优解，那么

是问题(3.1.1)的最优解。3.1.2等价问题目标函数与约束函数的变换例3.1.2最小化范数。作为一个简单的例子，考虑无约束的欧几里得范数极小化问题(3.1.9)其优化变量为。因为范数总是非负的，所以我们可以等价地求解问题(3.1.10)问题(3.1.9)和问题(3.1.10)显然是等价的，最优解相同。但是，这两个问题是不相同的。例如问题(3.1.9)的目标函数在任意满足的处都是不可微的，但问题(3.1.10)的目标函数对所有的都是可微的。如果令，，在上单调增大，则等价于。一般地，可以对目标函数和约束条件实施类似的变换。3.1.2等价问题松弛变量要注意等价于存在满足。利用这个变换，我们可以将优化问题(3.1.1)变形为(3.1.11)其中。这个问题有个变量，个不等式约束(关于的非负约束)和个等式约束。新的变量称为对应原不等式约束的松弛变量。通过引入松弛变量，可以将每个不等式约束替换为一个等式和一个非负约束。问题(3.1.11)与原标准形式问题(3.1.1)是等价的。是原问题(3.1.1)的最优解当且仅当是问题(3.1.11)的最优解，其中。3.1.2等价问题02凸优化模型凸优化问题的形式如下

(3.2.1)其中

为凸函数。和一般的标准形式(3.1.1)比较，凸优化问题有三个额外的要求：目标函数是凸函数。不等式约束函数是凸函数。等式约束函数

是仿射函数。注意到一个重要的性质：凸优化问题的可行集是凸的，因为可行集是问题定义域

(3.2.2)

(这是一个凸集合)、

个凸的水平集

以及

个超平面

的交集。不失一般性地假设

。因此，凸优化问题本质上是在一个凸集合上极小化一个凸的目标函数。3.2.1标准形式的凸优化问题凸优化问题的一个重要性质是其任意局部最优解也是全局最优解。这一点是凸优化模型在实践中取得成功的关键。为理解这点，设

是凸优化问题的局部最优解，即

是可行的并且对

，有

可行，

(3.2.3)现在假设

不是全局最优解，即存在一个可行的

使

。显然

，若该条件不成立，则有

。考虑由

(3.2.4)给出的点

，我们有

。根据可行集的凸性，

是可行的。根据

的凸性，有

(3.2.5)这与式(3.2.3)矛盾。因此不存在满足

的可行解

，即

是全局最优解。对于一般的非凸优化问题，局部最优解是全局最优解这一性质未必成立。基于这一性质，读者在建立优化模型时，在可能的情形下，应优先构建凸优化模型。否则，经典的优化算法通常仅能求解得到一个驻点或局部最优点，离全局最优点可能很远，不能保证应用于实际问题的效果。3.2.2局部最优解与全局最优解可微函数f0的最优性准则设凸优化问题的目标函数

是可微的，对所有的

，有

(3.2.6)

令

表示其可行集，即

(3.2.7)那么，

是最优解当且仅当

且

(3.2.8)这个最优性准则可以从几何上进行解释：如果

，那么

在

处定义了可行集的一个支撑超平面，如图3.2.1所示，其中可行集

由阴影表示，

的等值曲线由虚线显示，点

是最优解，

是

在

处的一个支撑超平面的法向量。3.2.3最优性条件图3.2.1最优性条件的几何解释最优性条件的证明首先假设

满足条件(3.2.8)。如果

，根据(3.2.6)式，我们有

。这表明

是问题(3.1.1)的一个最优解。反之，设

是最优解但条件(3.2.8)不成立，则存在

，满足

(3.2.9)

考虑点

，其中

为参数。因为

在

和

之间的线段上，而可行集是凸集合，因此

可行。对于较小的正数t，有

。这证明

不是最优的。为说明这一点，注意到

(3.2.10)

所以，对于较小的正数t，有

。证毕。我们将在后面章节中深入探讨最优性条件，在这里考察几个简单的例子。3.2.3最优性条件无约束优化问题对于无约束凸优化问题

(即

)，最优性条件简化为

(3.2.11)这是一个众所周知的凸优化问题的充要条件。有必要考察它是如何从条件(3.2.8)中得到的。设

为可行解，即

，且对于所有可行解

，都有

。因为

可微，其定义域是开集，所以所有充分靠近

的点都是可行的，取

，其中

为参数。当

为小的正数时，

是可行的，因此

(3.2.12)

因此

。例3.2.1解析中心。考虑关于凸函数

的无约束极小化问题。

(3.2.13)

其中

表示A的行向量。函数

可微，因此

是最优解的充要条件为

(3.2.14)

条件

即是

。如果

不可行，则

的定义域为空。3.2.3最优性条件只含等式约束的问题考虑只含等式约束的凸优化问题。

(3.2.15)

该问题的可行集是仿射集。假设

是上述问题的最优解，则对任意满足

的

，有

(3.2.16)都成立。因为

可行，每个可行解

都可以写作

的形式，其中

是A的零空间的向量，即

，因此，最优性条件可表示为

(3.2.17)如果一个线性函数在子空间中非负，则它在子空间上必恒等于零。因此，对于任意

，我们有

，即

(3.2.18)

由

得，最优性条件可表示为

，即存在

，使

(3.2.19)

再加上可行性条件

，便是经典的Lagrange乘子最优性条件。我们将在后面章节中更详细地研究这一条件。3.2.3最优性条件03线性规划二战中，受战争资源调配等问题的刺激，运筹学应运而生。线性规划作为一类特殊的凸优化问题被首先关注。它也是一只“会下金蛋的鸡”，许多著名的优化算法，如内点法，首先为求解线性规划问题而设计，随后在求解其他更一般的凸优化问题时也取得了成功。时至今日，人们已开发了众多软件包，可以高效求解大规模线性规划问题。当目标函数和约束函数都是仿射函数时，相应的优化问题称为线性规划(linearprogram，LP)。线性规划的一般形式如下。

(3.3.1)其中

，

。线性规划问题是特殊的凸优化问题。通常省略目标函数的常数

，因为它不影响最优集。LP的几何解释见图3.3.1，其中，可行集

是多面体，目标函数

是线性函数，它的等值线是与

正交的超平面(用虚线表示)，点

是最优解。3.3线性规划图3.3.1LP的几何解释常见的两种线性规划是标准型线性规划和不等式线性规划。在标准型线性规划形式如下。(3.3.2)其中不等式表示是分量的非负约束。如果LP没有等式约束，那么称这类问题为不等式线性规划，记为：

(3.3.3)3.3.1标准型线性规划和不等式线性规划为使用标准型线性规划算法，需要将一般的线性规划(3.3.1)转化为标准型(3.3.2)。第一步是为不等式引入松弛变量

。

(3.3.4)第二步是将变量

表示为两个非负变量

和

的差，即

。这就得到了下面的线性规划

(3.3.5)这是一个标准型线性规划，包含变量

和

。3.3.2线性规划转化为标准型线性规划在很多领域都有应用，下面给出一个典型的例子。例3.3.1线性规划求解切比雪夫中心考虑在多面体中寻找最大的欧式球问题。可以用线性不等式描述这个多面体。(3.3.6)最大球的中心称为多面体的切比雪夫中心，它是多面体内部最深处的点，即距离边界最远的点。可以把球表示为(3.3.7)这个问题中的变量是中心，半径为，希望在约束的基础上能够最大化。先考虑一个较简单的约束条件，即位于一个半空间内，即(3.3.8)因此(3.3.9)可以将(3.3.9)式写成关于和的不等式(3.3.10)即由约束不等式决定的球在半空间上的约束可以写成一个线性不等式。3.3.3线性规划应用举例因此

当且仅当(3.3.10)式对所有

都成立。切比雪夫中心可以通过求解下述关于

和

的线性规划来确定，(3.3.11)考虑下面的线性不等式组定义的多面体P：(3.3.12)实例代码3.3.1给出了基于线性规划求解该多面体的切比雪夫中心的代码。多面体及求得的切比雪夫中心，如图3.3.2所示。图3.3.2切比雪夫中心3.3.3线性规划应用举例04二次规划模型数据科学和机器学习中的许多模型，如最小二乘回归，支持向量机，均可以化为二次规划模型。如果目标函数为凸二次函数，约束函数为仿射函数，那么凸优化问题(3.2.1)称为二次规划(quadraticprogram，QP)。二次规划可以表示为以下形式。(3.4.1)其中。二次规划实际上是在一个凸多面体上最小化一个凸二次函数，如图3.4.1所示，其中，多面体表示可行集，目标函数的等值线用虚线表示，点是最优解。图3.4.1二次规划的几何图解3.4二次规划模型上述二次规划的不等式约束为线性约束，如果不等式约束函数是凸二次函数，则二次规划拓展为下述形式。(3.4.2)其中。这一问题称为带二次约束的二次规划(quadraticallyconstrainedquadraticprogram，QCQP)。它的可行域是多面体与若干个椭球相交的部分(当)。在(3.4.2)式中取，得到二次规划的特殊情况──线性规划。在(3.4.2)中取，可以发现QCQP包括二次规划，因此也包括线性规划。3.4二次规划模型最小二乘回归凸二次函数的最小化问题

(3.4.3)是一个无约束的QP。它应用于很多领域，并有解析解

，其中

是矩阵

的伪逆。当含有线性不等式约束时，这个问题被称为带约束的回归问题或约束最小二乘，不再有简单的解析解。下面的例子是变量有上下界的一个回归问题，也是一个二次规划问题。

(3.4.4)多面体之间的距离多面体

和

在

上的欧氏距离定义为

(3.4.5)如果多面体相交，则距离为零。通过求解下面的二次规划可以得到

和

之间的距离，优化变量

(3.4.6)

当且仅当其中一个多面体为空时，这个问题是不可行的。当且仅当多面体相交时，最优值为零，在这种情况下，最优解

和

相等(并且是

和

的交点)，否则最优解

和

分别是

和中彼此最接近的点。3.4.1二次规划的例子例3.4.1二次规划求多面体间的距离考虑多面体和多面体之间的距离。(3.4.7)(3.4.8)实例代码3.4.1给出了基于二次规划求解上述两个多面体之间距离的代码。

3.4.1二次规划的例子代码第13行输出求得的最优解为：[5.30e-04，1.00e+00，5.78e-04，2.00e+00]，表示两个多面体相距最近的两个点近似为

和

。图3.4.2展示了这两个多面体及其最相距最近的两个点。图3.4.2二次规划求多面体间的距离结果图3.4.1二次规划的例子与二次规划密切相关的问题是二阶锥规划(second-orderconeprogram，SOCP)。(3.4.9)其中是优化变量，。将如下约束形式称为二阶锥约束(3.4.10)其中。二阶锥约束要求仿射函数位于空间的二阶锥上。当时，SOCP(3.4.9)等价于QCQP。另外，如果，那么SOCP(3.4.9)就退化为线性规划问题3.4.2二阶锥规划例3.4.2考虑下面的二阶锥规划问题(3.4.11)我们通过调用Cvxopt包求解上述问题，见实例代码3.4.2，所求得的最优解为[5.01e+00，5.77e+00，8.52e+00]。05几何规划几何规划是一类可以转化为凸优化问题的模型，它在许多实际问题中有广泛应用。称为关于x的单项式，，，。多个单项式的和称为的多项式。下述关于多项式和单项式的优化问题称为几何规划(geometricprogram，GP)。(3.5.1)其中为多项式，为单项式。该问题的定义域为，隐式约束为。3.5几何规划有一些形式的问题很容易转化为几何规划。如果

是一个多项式，

是一个单项式，那么约束

可以表示为

，因为

是一个多项式，这就转化为一个形如

的约束条件，其中

为多项式，

。类似地，若

和

都是非零单项式函数，那么我们可以将等式约束

表示为

(因为

也是单项式)。另外，如果想要最大化一个非零的单项式目标函数，可以通过最小化它的逆实现。例如下面的问题(3.5.2)变量

，含有隐式约束

。将上面的模型进行简单的转换，就可以得到等价的标准形式的几何规划。(3.5.3)3.5.1几何规划的扩展一般情况下的几何规划不是凸优化问题，但可以通过变量变换等方法转化为凸优化问题。定义变量

，则

。如果

是关于

的单项式函数，

，那么

(3.5.4)

其中

。变量变换

可将单项式转换成一个仿射函数的指数函数(凸函数)。类似地，对于多项式

(3.5.5)

那么

(3.5.6)

其中

，且

。在变量转换后，多项式变成了仿射函数的指数和。几何规划(3.5.1)可以用关于新变量

的式子等价表示

(3.5.7)

其中

，

。通过取对数变换，得到如下问题。3.5.2几何规划转化为凸优化问题添加标题(3.5.8)由于是凸函数，是仿射的，所以这是一个关于的凸优化问题，称其为凸优化形式的几何规划，也称为正项几何规划。注意，多项式几何规划(3.5.1)与凸形式的几何规划(3.5.8)之间的转换不涉及任何计算，这两个问题是等价的。另外，如果多项式目标和约束函数都只有一项，即为单项式，则凸形式的几何规划(3.5.8)简化为线性规划。因此可以认为几何规划是线性规划的推广。3.5.2几何规划转化为凸优化问题考虑矩阵

，将

映射为

。缩放坐标，把变量变换为

，

，其中

为对角矩阵，

。在新坐标下，

。考虑选择一种缩放方式，使矩阵

很小。使用Frobenius范数的平方来度量矩阵的大小。(3.5.9)其中

。这是关于d的一个多项式，因此选择尺d来最小化Frobenius范数的问题是一个无约束的几何规划。

(3.5.10)变量为d，这个几何规划中的指数是

。请读者尝试调用cvxopt包求解上述问题对应的凸形式的几何规划。3.5.3几何规划的例子06广义不等式约束若不等式约束函数为向量值，并在约束中使用广义不等式，可以得到标准型凸优化问题(3.2.1)的一个重要的推广。(3.6.1)其中

是点锥，

是

-凸锥。把这个问题称为带有广义不等式约束的标准型凸优化问题。若

，则问题(3.6.1)退化为标准型凸优化问题(3.2.1)。具有广义不等式约束的优化问题具有一般凸优化问题的很多性质，例如：可行集、任意水平集、最优集均为凸集。问题(3.6.1)的任何局部最优的点都是全局最优点。对于可微函数

在3.2.3节中给出的最优性条件仍然成立。实际上，带有广义不等式约束的凸优化问题通常像普通的凸优化问题一样容易求解。3.6广义不等式约束在带广义不等式的凸优化问题中，最简单的是线性锥规划问题，它有一个线性目标和一个仿射的不等式约束函数(因此是

-凸锥)。(3.6.2)当

为非负卦限(锥)时，锥规划问题退化为线性规划问题。可以把线性锥规划问题视为线性规划的一种推广。类似于线性规划，下面的锥规划问题称为标准型线性锥规划问题。(3.6.3)下面的问题称为不等式形式的线性锥规划问题。(3.6.4)3.6.1锥规划问题当

为

时，半正定

矩阵联合锥规划问题称为半定规划(Semi-definiteProgramming，SDP)，具有如下形式。(3.6.5)其中

。这里的不等式是一个线性矩阵不等式。如果

矩阵都是对角矩阵，那么(3.6.5)中的线性矩阵不等式等价于

个线性不等式，SDP(3.6.5)退化为线性规划。3.6.2半定规划标准型SDP和不等式构成的SDP与线性规划类似，标准型SDP有线性等式约束，对变量

有非负矩阵性束。(3.6.6)其中

，

是

上的一般实值线性函数形式。与标准型线性规划(3.3.2)比较，在LP和SDP的标准型中，目标函数都是变量的线性函数，变量有

个线性等式约束和一个非负约束。与不等式线性规划(3.3.3)类似，不等式形式的SDP没有等式约束，只有一个线性矩阵不等式约束。(3.6.7)其中

。3.6.2半定规划SDP在组合优化中具有广泛的应用。许多NP-难组合优化问题进行凸松弛后可以化为半定规划问题。许多实例进行SDP松弛后，所得到的界是非常紧的。特别是在某些实例中，SDP松弛问题的最优解可以转换成原来问题的一个可行解，并且可以证明这个可行解具有较好的目标函数值。下面是组合优化中应用SDP的一个例子。最大割问题的半定规划松弛设

是一个无向图，顶点集合为

，边的集合为

。设

为边

上的权值，其中

。假设对于所有的

，都有

。最大割问题是指确定顶点集合N的一个子集

，使连接顶点子集

到它的余集

(其中

)的所有的边权值之和最大。3.6.3组合优化中的SDP若，则令，否则，令，可以将最大割问题描述为如下的整数规划问题。(3.6.8)令，其中。令为权矩阵，即其第行，第列的元素为，则最大割问题可以等价地描述为(3.6.9)注意到在上述问题中第一部分约束等价于，因此可得(3.6.10)最后注意到矩阵是一个秩为1的半正定矩阵，如果将这一条件进行松弛，即去掉秩为1这一限制，则可以得到如下的最大割问题的半定规划松弛问题。(3.6.11)3.6.3组合优化中的SDP已知松弛问题(

)为最大割问题(

)提供了一个上界，即：事实上，可以证明下面的不等式成立这个结果表明半定规划松弛问题的最优值与最大割这一NP难问题的最优值相差不超过13%。实例代码3.6.1给出了半定规划求解最大割问题的示例，其中有5个结点，如图3-6所示。3.6.3组合优化中的SDP图3.6.1最大割问题示意图实例代码3.6.1调用cvxpy包求解最大割问题的半定规划松弛问题。3.6.3组合优化中的SDP实例代码3.6.1所求得的最优值是-20.1334，最优解X为[[1.0.59829309-0.83092504-0.886349620.82789529][0.598293091.-0.9429549-0.901301540.94474659][-0.83092504-0.94295491.0.99410527-0.99998527][-0.88634962-0.901301540.994105271.-0.99350263][0.827895290.94474659-0.99998527-0.993502631.]]从结果可以看出节点0,1,4应该分为一类，节点2,3分到另一类。谢谢观看对偶理论最优化模型与算法——基于Python实现第四章01Lagrange对偶函数考虑标准型的优化问题：(4.1.1)其中，变量

，假设其定义域

为非空，将该问题的最优值记作

，我们不对这个问题作凸性的假设。Lagrange对偶性的基本思想是运用(4.1.1)中约束条件的加权求和对目标函数进行扩充，从而将约束条件考虑在内。问题(4.1.1)的Lagrange函数

定义为：

(4.1.2)

其定义域为

。将对应于第

个不等式约束条件

中的

称为Lagrange乘子；类似地，

是对应于第

个等式约束

的Lagrange乘子。向量

和向量

称为优化问题(4.1.1)的对偶变量或Lagrange乘子向量。4.1.1Lagrange函数定义4.1.1Lagrange对偶函数(简称对偶函数)

定义为Lagrange函数关于

的最小值：对于

，

，(4.1.3)当关于

的Lagrange函数无下界时，其对偶函数取值为

即使当问题(4.1.1)为非凸时，因为对偶函数是仿射函数族

的逐点下确界，所以对偶函数是凹函数。4.1.2Lagrange对偶函数对偶函数给出了问题(4.1.1)的最优值

的下界：定理4.1.1对任意的

和任意的

，

(4.1.4)证明：假设

是问题(4.1.1)的一个可行点，即满足

和

，并且

，可得

(4.1.5)因为第一项求和中的每一项都是非正的，并且第二项求和中的每一项都为零，所以

(4.1.6)

因此

(4.1.7)

因为

对所有的可行点

都成立，故不等式(4.1.4)成立。“”4.1.3最优值的下界图4.1.1用

并且有一个不等式约束的简单问题解释了不等式(4.1.4)中的下界，实线表示目标函数

，虚线表示约束函数

。可行集合为区间[-1,1]，由两条垂直的点线表示。最优点和最优值分别是

(如图中圆点所示)。由点组成的曲线表示当

时的

。由于在可行集合上对

有

，因此每一个函数

的最小值都比

小。图4.1.1一个对偶可行点的下界不等式(4.1.4)成立，但是，只有当

且

时对偶函数能够给出非平凡下界

，即

。因此将

且

的数对

称为对偶可行的，下节中将给出更清晰的表述。4.1.3最优值的下界在此给出一个可以推导出Lagrange对偶函数的解析表达式的例子：线性方程的最小二乘解。考虑如下问题(4.1.8)其中

。这个问题没有不等式约束，只有

个线性的等式约束。Lagrange

，其定义域为

。其对偶函数

。因为

是关于

的二次凸函数，所以可以通过最优性条件

(4.1.9)

找到最小值点

。因此，对偶函数

(4.1.10)是一个定义在

上的凹二次函数。下界性质(4.1.4)表明，对任意

，有

(4.1.11)4.1.4Lagrange对偶函数的例子02Lagrange对偶问题对于每一组

，

，Lagrange对偶函数给出了优化问题(4.1.1)的最优值

的下界，因此能够得到依赖于某些参数

的下界。一个很自然的问题是：能够从Lagrange对偶函数中求得的最好的下界是什么？由此产生了下面的优化问题(4.2.1)这个问题被称为问题(4.1.1)的Lagrange对偶问题。初始问题(4.1.1)通常被称为原问题。数对

，

和

称为对偶可行的。正如名字所示，

对于对偶问题(4.2.1)是可行的。同时将问题(4.2.1)的最优解

称作对偶最优解或最优Lagrange乘子。Lagrange对偶问题(4.2.1)是一个凸优化问题，因为它最大化凹的目标函数，而且它的约束是凸函数。因此，无论原问题(4.1.1)是否是凸的，对偶问题都是凸优化问题。4.2Lagrange对偶问题上面的例子表明，对偶函数的定义域(4.2.2)其维度通常小于。在很多情况下，可以识别出的仿射包，并且将其描述为线性等式约束的集合。例如，在这些等式约束明确作为约束而给出的情况下，能够得到一个有等式约束的优化问题。下面的例子将阐释这一点。LP标准型的Lagrange对偶LP标准型为(4.2.3)其Lagrange对偶函数为(4.2.4)严格来讲，LP标准型的Lagrange对偶问题是在的约束下最大化对偶函数，(4.2.5)只有当时，是有限的。通过明确这些等式约束，可以构造一个等价问题：(4.2.6)通过变换，这个问题等价地表述为(4.2.7)这就是LP的不等式形式。4.2.1对偶约束注意这三个问题之间的细微区别。LP标准型(4.2.3)的Lagrange对偶是问题(4.2.4)，这与问题(4.2.6)和(4.2.7)等价，但并不相同。问题(4.2.6)或问题(4.2.7)称作LP标准型(4.2.3)的Lagrange对偶。不等式形式LP的Lagrange对偶同样地，能够得到不等式形式LP的Lagrange对偶问题(4.2.8)Lagrange函数为(4.2.9)所以其对偶函数是(4.2.10)一个线性函数除了当其恒等于零这一特殊情况，其下确界是，所以对偶函数可写作(4.2.11)当且时，其对偶变量是可行的。4.2.1对偶约束LP的Lagrange对偶(4.2.8)是对所有的

最大化

。类似地，可以通过明确地将对偶可行性条件作为约束条件包含进去，来重新构造对偶函数如下(4.2.12)该问题正是标准型LP。注意到LP标准型和不等式形式LP以及他们的对偶函数之间的对称性：LP标准型的对偶问题是一个只有不等式约束的LP，反之亦然。亦可以证明，问题(4.2.12)的Lagrange对偶问题等价于原问题(4.2.8)。4.2.1对偶约束定理4.2.1Lagrange对偶问题的最优值，用来表示，是能够从Lagrange对偶函数中得到的中最好的下界，即有如下不等式(4.2.13)即使原问题是非凸的，该不等式依然成立，这个性质叫作弱对偶性。这个性质虽然简单但是非常重要。当和无限时，弱对偶不等式(4.2.13)依然成立。例如，如果原问题无下界，即，则必有，即Lagrange对偶问题是不可行的。相反地，如果对偶问题无上界，即，则必有，即原问题是不可行的。4.2.2弱对偶性将两者的差值称为原问题的最优对偶间隙，因为它给出了原问题的最优值与从Lagrange对偶函数给出的最优下界之间的距离。最优对偶间隙总是非负的。弱对偶性有时可以被用来寻找难以解决的问题的最优值下界，因为其对偶问题总是凸的，并且很多情况下能够有效求解并找到。例如，考虑双向分配问题，其对偶问题是半正定规划，(4.2.14)其中变量。对于相对较大的值，比如，这个问题也能被有效解决。最优值是双向分配问题的最优值的很好的下界。4.2.2弱对偶性如果等式

(4.2.15)成立，即最优对偶间隙为0，则称强对偶性成立。这意味着通过Lagrange对偶函数得到的最优下界是紧的。通常情况下，强对偶性未必成立。如果原问题(4.1.1)是凸的，即满足如下形式(4.2.16)其中

是凸函数。为了使强对偶性成立，要求问题(4.2.16)的可行域满足一些假设条件。这些条件称为约束规范。一个简单的约束规范是Slater条件：存在

使得

(4.2.17)

4.2.3强对偶性与Slater约束规范这样的点有时被称为严格可行的，因为不等式约束在严格不等式时成立。Slater定理表明，当Slater条件成立并且问题是凸问题时，强对偶性成立。如果一些不等式约束函数

是仿射函数，Slater条件可以进一步弱化。若前

个约束函数

是仿射的，则在下面较弱的条件成立时，强对偶性成立：存在

，使得

(4.2.18)即仿射不等式不需要与严格不等式同时成立。Slater条件以及弱化的条件(4.2.18)不仅蕴含了凸问题的强对偶性，它还表明当

是有限值时能够取得对偶最优值，即存在一组对偶可行的

使得

。可以证明，当原问题是凸的且Slater条件成立时，强对偶性成立。4.2.3强对偶性与Slater约束规范03Lagrange对偶的理解对一组

，如果

(4.3.1)对所有

成立，我们称

为

的鞍点。换言之，

使

最小(对所有

)并且

使

最大(对所有

)：

(4.3.2)这表明强最大最小性质

(4.3.3)成立，它们的共同值是

。对于Lagrange对偶可以发现，如果

和

是一个满足强对偶性问题的原始最优点与对偶最优点，则(

,

)构成Lagrange函数的鞍点，反之仍然成立。如果

是Lagrange函数的鞍点，那么

为原始最优解，

为对偶最优解，并且最优对偶间隙为0。4.3.1鞍点可以将最大最小不等式

(4.3.4)和最大最小等式(4.3.3)以及鞍点性质，表述为连续的零和博弈。如果玩家1选择

，玩家2选择

，那么玩家1支付数量为

的报酬给玩家2。因此玩家1想要最小化

，而玩家2想要最大化

。因为

是连续的，所以这个博弈称作连续博弈。假设玩家1首先做出决定，随后玩家2在了解了玩家1的选择后制定选择。玩家2想要最大化得到报酬

，因此会选择能够最大化

的

。最终的报酬为

，这取决于玩家1做出的选择(我们在假设上确界能够取到，如果不能，最优的报酬能够任意接近

)。假设玩家1知道玩家2会跟随其做出策略，因此会选择

来使支付给玩家2的报酬在最坏的情况下尽可能少。因此玩家1选择

(4.3.5)这将使玩家1向玩家2支付的报酬为

(4.3.6)4.3.2博弈论解读4.3.2博弈论解读现在假设玩家顺序相反：玩家2必须首先选择

，随后玩家1在知道

的情况下选择

。按照同样的分析，如果玩家们遵循最优策略，玩家2会选择能够最大化

的

，这将使玩家1向玩家2支付的报酬为

(4.3.7)最大最小不等式(4.3.4)表明这样一个直观上明显的事实。对于玩家来说，第二个进行选择更好，或者说，在选择之前已经知道对手选择的玩家更有利，即如果玩家1先选择，那么玩家2得到的报酬更大。但当鞍点性质(4.3.3)成立时，第二个选择的玩家实际上没有优势。如果

是

关于

和

的鞍点，那么它被称为博弈的解。

叫作玩家1的最优选择或最优策略，

叫作玩家2的最优选择或最优策略。在这种情况下，第二个选择的玩家没有优势。现在考虑特殊情况，支付