最优化理论与算法(第八章).doc

第八章 约束优化最优性条件

§8.1 约束优化问题
一、 问题基本形式

（8.1）
特别地，当为二次函数，而约束是线性约束时，称为二次规划。
记 ，称之为可行域（约束域）。
，，
称是在处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints）。
应该指出的是，如果是（1）的局部最优解，且有某个，使得

则将此约束去掉，仍是余下问题的局部最优解。
事实上，若不是去掉此约束后所得问题的局部极小点，则意味着，存在，使得，且，这里满足新问题的全部约束。注意到当充分小时，由的连续性，必有，由此知是原问题的可行解，但，这与是局部极小点矛盾。
因此如果有某种方式，可以知道在最优解处的积极约束指标集，则问题可转化为等式的约束问题：

（8.2）
一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道。
§8.2 一阶最优性条件
一、几种可行方向
定义8.1 设，是一非零向量。如果存在，使得，
则称是处的一个可行方向。在处的的所有可行方向的集合记为
定义8.2 设，若满足：
（8.3）
（8.4）
则称是处的线性化可行方向。在处的的所有线性化可行方向的集合记为。
定义8.3 设，，若存在序列和，使得对一切，有，且，，则称是处的序列可行方向。在处的的所有序列可行方向的集合记为。
引理8.4 设，且所有约束函数都在处均可微，则有：
（8.5）
证明： 对任何，由定义8.1可知，存在使得
，
令 ，和
则显然有 ，且 ，
因而，由的任意性，即知。
又对任何，如果，则显然。假定，由定义8.3，存在序列和，使得，且和。由有，

在上两式的左右两端除以，然后令趋于无穷，即得满足

因而，由的任意性，即知，证毕。

二、一阶最优性条件
引理8.5 设是问题（8.1）的局部极小点，若和都在处可微，则必有，。
证明：对任何，存在序列和，使得
，且和。
由，而且是局部极小点，故对充分大的有：

由上式可知，，引理于是证毕。
引理8.5表明：在极小点处，所有的序列可行方向都不是下降方向。
引理8.6 （Farkas引理）线性方程组和不等式组

无解的充要条件是存在实数和非负实数使得：
（8.9）
证明：假定（8.9）式成立，且，那么对任意满足（8.6），（8.7）的，都有

因而不等式组无解。
另一方面，若不存在实数，非负实数，使（8.9）式成立。考虑集合：

易证是中的一个闭凸锥，且。由凸集分离定理：必存在，使得
（是一常数）
由于，所以。又由于是锥，故，有，从而
因而必有
再由
有
类似可得 ，
亦即
由以上讨论可见，是不等式组（8.6）——（8.8）的一个解。
注： 这里介绍的Farkas引理，以及其他教科书上给出的择一定理、Motzkin定理与Gordan定理，均是由凸集分离定理得出的同一类定理，它们在导出约束最优性条件方面起着至关重要的作用。
定理8.7（Karush-Kuhn-Tucker定理）设是（8.1）的局部极小点，若，则必存在，使得：
（8.10）
证明：由引理8.5，，有，因而 ，有。由的定义，知

无解。由Farkas引理，知存在和，使得

再令 ，即得，且满足。
注：1) 称为Lagrange函数，称为Lagrange乘子；
2）（8.10）通常称为问题（8.1）的K-T-T条件（或K-T条件），而满足（8.10）的点称为K-T-T点（或K-T点），（8.10）中的第二式称为互补松弛条件；
3）当约束规范性条件不成立时，局部极小点不一定是K-T点。

三、的一些充分条件
定理8.8 若所有的都是线性函数，则。
证明：，有

取，，那么当时，有

当时，有
而当时，由知：当充分大时（），有
。
即有
这表明
即
再由，即得，证毕。

定理8.8 若1) 线性无关；
2）集合非空。
则。
证明：先证
设是中任一向量，令是子空间的正交补中的标准正交基。（由，故与正交，因而上述生成子空间的维数为）。
考虑下面以为参数的非线性方程组
（8.11）
它将确定以为参数的一个隐函数。由于在处，上述方程组的Jacobi矩阵非奇异，且是方程组的解。根据隐函数定理，对充分小的，必存在解且满足
。
事实上，将方程组确定的隐函数对求导，有

令，得

上述方程组得系数矩阵非奇异，故有唯一解，又显然方程组的解，因而有。
下证当充分小时，。事实上，由是由方程组（8.11）确定的隐函数，由方程组（8.11）的第一式知，

当时，由的定义，有

故当充分小时，有

最后一个不等式是由于时，

当时，由。故当充分小（）时，有 。
因此有。
现取
则有 （，）
由上面分析，
这表明 ，或
由是中任意向量，故。再由是闭集（可直接验证），故有

注意到
从而得： ，定理证毕。
定理8.9 若在处线性无关，则。
证明：1）若是空集，则易知上一定理的条件满足，从而结论成立。
2） 若非空，那么对任何，由于线性无关，必存在，使得： （，），。
事实上，若记，则线性无关。记是

的一组标准正交基。取

则与正交，即与正交。因此有：

而
因而取
即满足要求，对每个，均可仿此构造出。令
，
易证：，即非空，由上一定理有：
。
注：定理8.9 是最重要、最常用的约束规范性条件。

四、一阶充分性条件
定理8.10 设，若和在处都可微，且
，（） （8.12）
则是问题（8.1）的严格局部极小点。
证明：假定（8.12）成立，而不是局部严格极小点，则存在，使得
（8.13）
且有
不失一般性，可设 （否则，取其收敛子序列）。
令
即知
再由（8.13），有
其中，位于由与确定的线段上。进而有

在上式中，令，即得

这与（8.12）矛盾。定理于是证毕。
推论 设，若和在处都可微，且
，（） （8.14）
则是问题（8.1）的严格局部极小点。

五、Fritz-John必要条件
定理8.11 设，在上连续可微，若是问题（8.1）的局部极小点，则必存在，，使得

注：1) Fritz-John必要条件对约束不附加任何条件（即不要求约束满足约束规范性条件）；
2) 时，是K-T条件；时，目标函数从条件中消失。这是条件仅描述了约束条件之间的关系，使得到的Fritz-John点不是极小点的可能性增大，则也是Fritz-John条件不如Karush-Kuhn-Tucker条件使用广泛的原因；
3）证明可参见俞玉森等著《数学规划原理和方法》。

§8.3 二阶最优性条件
1）若且，都有，则由前一节的充分性条件知是局部严格极小点；
2）若，使，则是处的一个下降可行方向，因而不是极小点。
以上两种情形都可得到确定的结果，但若这两种情形都不出现，即
， （8.15）
且 ，（）使 （8.16）
如果仍假定约束规范性条件满足，那么类似定理8.7的证明可知是K-T点。记是相应的Lagrange乘子，显然对使（8.16）成立的，有
。
由，知，由上式可推出
，。
由此，引入下述定义
定义8.12 设是K-T点，是相应的Lagrange乘子，若，且满足：

则称是在处的线性化零约束方向。处所有线性化零约束方向记为。若处的Lagrange乘子唯一，则简记为。
定义8.13 设是K-T点，是相应的Lagrange乘子，如果存在向量序列和数列，，使得 ，
且有，，则称是在处的序列零约束方向，处的序列零约束方向的集合记为。
由定义显然有：

且类似于
有
下面证明这一结论。事实上，任取，由的定义知，存在
，（）
使 ，
且 （这里，对应的）
。
将在处展开，则有
1）若，

两边除，令，得
2）若，

类似可得：
故有
由的任意性，有 。
注：1）；
2）若，则存在，，，，使得
且，；，。

二阶最优性条件
定理8.14 设是局部极小点，是对应的Lagrange乘子，则必有，使得
，
其中是Lagrange函数。（二阶必要条件）
证明：（略）
定理8.15 设是一个K-T点，是对应的Lagrange乘子。如果，
，
则是局部严格极小点。（二阶充分条件）
证明：（略）
注：1）一阶充分性条件与二阶充分性条件不是谁比谁弱的关系，彼此之间不存在简单的逻辑蕴含。
2）对一阶充分性条件，，。若出现某些，使，这时一阶条件无效，可以转而考察二阶条件。

§8.4 凸规划问题
定义8.16 若为凸集，为上的凸函数，则称
（8.17）
为凸规划。在
（8.18）
中，若，均为凸函数，则为凸集，从而上述问题为凸规划问题。
注：在（8.18）中没有考虑等式约束。事实上，在凸规划问题中，若包含等式约束，则该约束必为线性约束，因而为简单计，假定不含等式约束，对于包含等式约束的凸规划问题，所有讨论只须稍作修正，则同样有效。
定理8.17 若在（8.18）中，均为凸函数，则其任何局部最优解均为全局最优解。
证明：设为局部最优解，若它不是全局最优解，则必存，使得
，有
当时，，落入的邻域，但

这与为局部最优解矛盾，所以必为全局最优。
定理8.18 若为严格凸函数，而均为凸函数。若（8.18）有最优解，则必唯一。
证明：设是（8.18）的最优解，而是另一最优解。于是，，因而有
这与为最优解矛盾，故最优解唯一。
定理8.19 设，均为凸函数，且在可微，又是问题的K-T点，则是全局最优解。
证明：由在上凸，故，有

再由的凸性，有

当时，，而，故有
，
而当时，由互补松弛条件，有，
故有
因此有
所以是全局最优解。
§8.5 凸规划的对偶理论
和线性规划一样，对偶理论在非线性规划的理论与算法研究中也起着重要作用。由于构造对偶问题的不同方法，因而有不同的对偶理论。如Rockafellare对偶理论，Wolfe对偶理论，Fenchel对偶理论。这里只介绍Wolfe对偶理论，一方面是因为它比较简单，从计算的观点看较为方便。另一方面，它也是目前文献中最常采用的对偶形式。
考虑非线性规划问题（NLP）：

记，称函数：

为对偶目标函数，而称问题（DNLP）

对原问题的对偶问题。
对一般非线性规划问题，对偶问题的形式比较复杂，较难处理。但当，均为上的凸函数时，由于为凸函数，而且，
，
其中由解出。因而对偶问题可化为（DNLP1）：

对偶理论
设原问题为：
对偶问题为：
1） 若是原问题的可行解，是对偶问题的可行解，则有，即总有，这就是所谓弱对偶定理。
2） 若进一步有，即，则与是分别是原问题与对偶问题的最优解。

这就是所谓强对偶定理。
§8.6 鞍点问题
对任一非线性规划问题，可以考虑下面三个密切相关的问题。
1）原始不等式约束问题（PP）

2） 广义Lagrange问题（K-T条件）
记

3）鞍点问题（SP）
求，（），使得，及都有
，
称为的鞍点。
定理8.20 设，可微，是（PP）的最优解。若在处满足约束规范性条件，则必存在Lagrange乘子，使得是K-T问题的解。
定理8.21 若，可微凸，且是K-T问题的解，则是（PP）的最优解。
定理8.22 若，可微，是鞍点问题（SP）的解，则它是K-T问题的解。
定理8.23 若，可微凸，是K-T问题的解，则它必是鞍点问题的解。
定理8.24 若是鞍点问题的解，则是（PP）的最优解。
定理8.25 若，可微凸，是（PP）的最优解，且在处满足约束规范条件，则存在，使是鞍点问题的解。
注：以上诸定理的证明可参阅魏权龄等著《数学规划引论》第4章的相关内容，这里从略。