最优化方法第四章

第4章约束最优化方法在第2章中已讨论过带有约束的线性规划问题，而本章要讨论的则是带有约束的非线性规划问题，其一般形式为（4.1）其中

。这个问题的求解是指，在容许集内找一点，使得对于任意的，都有点

称为问题（4.1）的最优解。由于带有了约束，使得对约束最优化问题（4.1）的求解变得比对无约束最优化问题（3.1）的求解复杂得多，也困难得多。本章将讨论求解约束最优化问题常用的两类最优化方法。一类是所谓的容许方向法。它是一种直接处理约束的方法。另一类是所谓的罚函数法。相对前者而言，它是一种直接处理约束问题本身的方法，其主要特点是用一系列无约束问题的极小点去逼近约束问题的最优点。在4.1节中将首先讨论约束问题的最优性条件，为后面算法的终止准则提供理论依据；在4.2-4.3节中将讨论二种容许方向法，包括Zoutendijk容许方向法、Rosen梯度投影法；在4.6-4.8节中将讨论三种罚函数法，它们是外部罚函数法、内部罚函数法和乘子法。

4.1最优性条件所谓最优性条件，就是最优化问题的目标函数与约束函数在最优点所满足的充分条件和必要条件。最优性必要条件是指，最优点应该满足的条件；最优性充分条件是指，可使得某个容许点成为最优点的条件。最优性条件对于最优化算法的终止判定和最优化理论的推证都是至关重要的。本节仅讲述最基本的结论。在第2章和第1章中，已经分别讨论过线性规划问题和无约束问题的最优性条件。定理2.9是线性规划问题的最优性充分条件。定理1.15、定理1.17和定理1.18以及推论1.16分别是无约束问题的最优性必要条件、充分条件以及充分且必要条件。本节主要讨论一般约束问题的最优性条件。我们将先从仅含等式约束或不等式约束的问题入手，然后自然过渡到一般约束问题。1.等式约束问题的最优性条件考虑仅含等式约束的问题

（4.2）这个问题的最优性条件与求解方法在微积分中已从理论上得到了解决，这就是Lagrange定理和Lagrange乘子法。定理4.1（Lagrange定理）

P217Lagrange乘子法定义函数称为Lagrange函数，其中称为Lagrange乘子，则求解等式约束问题（4.2）等价于求解无约束问题(4.4)Lagrange函数（4.4)的梯度是其中最优性必要条件及下面的定理给出了（4.2）的最优性二阶充分条件。定理4.2P2182.不等式约束问题的最优性条件（1）几何最优性条件下面将给出约束问题

（4.7）的最优性条件。设容许集仍用表示，即以下几个概念是讨论的基础。定义4.1对于约束问题（4.7），设

。若使得某个不等式约束有

，则该不等式约束称为是关于容许点

的起作用约束；否则，若

则该不等式约束称为是关于容许点的不起作用约束。

，例如，不等式约束关于容许集的任意内点都是不起作用约束。只有容许集的边界点才能使某个或某些不等式约束变为起作用约束。定义4.2设是中的非空集，且

。对于，若当

时，对于，必有

，则集合称为以为顶点的锥。若锥是凸集，则称为凸锥。

显然，由维向量的全部非负组合构成的集合是一个以原点为顶点的凸锥。由于这样的凸锥的边界是（超）平面或直线，所以也称为由

凸多面锥。张成的定义4.3设是中的非空集，且

。对于非零

向量，若存在，当时，必有

，则称为点

的容许方向向量，其方向

称为点的容许方向。由点的全部容许方向向量构成的的容许方向锥，记作集合称为点引理4.3设

；并设当时，在点

处可微，当时，

在点处连续。若对于所有的，向量使得，则是点的一个容许方向向量。证考虑某个

。因为，所以是在点处的上升方向。根据定义1.10，存在

,例如，当时，。

再考虑某个。因为

，且在点

处连续，故存在，当时，。取，则当

时，对于所有的必有

，即。根据定义4.3，即是点的容许方向向量。记，则依引理4.3可知，。由这个引理看到一个事实，若仅使某个约束，例如

，变成起作用约束，且，而其它约束是不起作用约束，则

就是点的一个容许

方向向量。换句话说，约束曲面

把整个空间分成总是指向包含容许集的那一侧。两部分，梯度，由点的所有下降方向向量构成的集合称为点下降方向锥。的定理4.4设在点处可微，则点下降方向向量必满足的记，则定理4.4表明，既是点的下降方向锥。显然是中的半空间。下面的定理给出的约束问题（4.7）的最优性条件是仅借助点集的概念给出的，所以称为几何最优性条件。定理4.5在约束问题（4.7）中，若是局部最优点，处的容许方向锥和下降方向锥的交集是空集。则点这个定理表明：在最优点处，一定不存在下降容许方向。

换句话说，在最优点处，或者不存在下降方向，或者任何下降方向都不是容许方向。定理4.6在问题（4.7）中，假设：i）是局部最优点，ii）在点处可微；当时，在点

可微，当时，在点处连续。那么，处证根据引理4.3，若

，则，

从而。又根据定理4.5，有故必有。例4.1P222定理4.5和定理4.6给出的最优性条件仅仅是必要的，而不是充分的。习题4.6和习题4.7可以说明这一点。几何最优性条件直观易懂，但在实际计算中使用起来并不简便。以下讨论的Fritz-John条件和Kuhn-Tucker条件是经常用到的最优性条件。（2）Fritz-John条件首先介绍两个引理，这两个引理本身在最优化理论中处于很重要的地位。引理4.7（Farkas）设和是维向量，则满足的向量也满足的充要条件是，存在非负数，使得Farkas引理的几何解释：Farkas引理指出，向量与凸多面锥（个半空间的交集）中任意向量都交成锐角或直角的充要条件是，向量

位于凸多面锥

之中。例如，见上图，位于中，它与中的任意向量都交成锐角；

不在中，它就不与中的所有向量交成与交成钝角。锐角或直角，如引理4.8（Gordan）设是维向量，使得则不存在向量成立的必要条件是，存在不全为零的非负数使得Gordan引理的几何意义：不存在向量使得在几何上表示向量

的某一非负线性组合为零向量。例如，在左下图中，取

，可使

右下图中，则找不到不全为零的非负数使得。

；在定理4.9（Fritz-John）在问题（4.7）中，设是在点处可微。，使得局部最优解，那么，存在不全为零的实数（4.9）

其中称为互补松弛条件。它表明：

若，即，则必有；若，则，即。必有这个定理给出了问题（4.7）的一个最优性必要条件。（4.9）称为问题（4.7）的Fritz-John条件，满足Fritz-John条件的点称为Fritz-John点。（4.9）中的也称为Lagrange乘子。

例4.2考虑约束问题试验证是Fritz-John点，不是Fritz-John点。解参看例4.1，在点处，。计算取，则有这表明是Fritz-John点。再考虑点，这时。计算根据（4.11），只须说明不存在不全为零的非负数，使得事实上，（4.12）式可写为（4.12）（4.13a）

（4.13b）

由（4.13a）得，而由（4.13b）有

，这若取非零值，则必异号。

一关系表明，这就是说，

不可能存在不全为零的非负数使得（4.12）成立，

即不是Fritz-John点。Fritz-John条件仅是判断容许点是否为最优点的必要条件，而不是充分条件。看下面的例题。例4.3考虑约束问题解显然是此问题的唯一最优点。因为在直线上，约束

关于所有容许点的梯度都等于零，所以当取时，总有（4.14）

如果除去点和点（这两点的起作用约束不止）

，那么（4.14）说明在直线其余的容许点都满足Fritz-John条件。但除了其它的点全不是最优点。上，外，（3）Kuhn-Tucker条件首先讨论一个例题。例4.4P227总结：Fritz-John条件失效的一个原因是，起作用约束函数的梯度线性相关。为保证

一定在Fritz-John条件中出现，即必须保证

，这可以通过附加上起作用约束函数的梯度线性无关的条件——Kuhn和Tucker提出的条件。实际上，为了保证

，还可以对起作用约束函数的梯度附加其它形式的条件，这样的一些条件在最优化理论中称为约束品性。定理4.10（Kuhn-Tucker）P227在起作用约束函数的梯度线性无关的前提下，公式（4.15）称为Kuhn-Tucker条件，而满足此条件的点称为Kuhn-Tucker点。Kuhn-Tucker条件的几何意义：在公式（4.15）中，删去不起作用约束项（注意，它们的系数是

Kuhn-Tucker条件可简写为：存在

）,，使得

（4.17）该式在几何上表示：若是问题（4.7）的最优点，则根据Farkas引理可知，目标函数在该点的梯度必位于由起作用约束函数的梯度所张成的凸锥之中。例如，书上图4-9显示，在点

处处于由和张成的凸锥之中，因此

满足Kuhn-Tucker条件，所以它有可能是最优点。如图所示，

确实是最优点。但在

处，不在由

和所张成的凸锥之中，

Kuhn-Tucker条件，因此肯定不是最优点。就不满足例4.5说明例4.2中的是Kuhn－Tucker点。解由例4.2中的求解知是Fritz-John点，且。又是线性无关的，所以由是Kuhn-Tucker点。定理4.10可知，3