最优化方法第四章

4.6外部罚函数法

4.2-4.5节介绍的容许方向法对于带有非线性约束的最优化问题的求解效果不甚理想。以下三节将针对一般约束最优化问题，给出一种有效的求解方法——罚函数法。它的特点是根据问题的约束函数和目标函数，构造一个具有“惩罚”效果的目标函数序列，从而把对约束最优化问题的求解转化为对一系列无约束问题的求解。这种“惩罚”策略，对在无约束问题求解过程中企图违反约束的那些迭代点给予很大的目标函数值，迫使这一系列无约束问题的极小点（即迭代点）或者无限地向容许集靠近，或者一直保持在容许集内，直到收敛到约束问题的极小点。考虑一般约束最优化问题（4.67）

4.6-4.8节将分别介绍三个罚函数方法。一是外部罚函数法（又称外点法）。其惩罚方式是对那些违反约束的点在目标函数中加入相应的“惩罚”，而对容许点不予惩罚。特点是迭代点一般在容许集外移动。二是内部罚函数法（又称内点法）。它仅适用于具有不等式约束的最优化问题。其惩罚方式是对那些企图从内部穿越容许集边界的点（容许集的内点）在目标函数中加入相应的“障碍”，而且点距边界越近，障碍也越大，对于边界上的点给予无穷大的障碍，从而保证迭代点一直在容许集内移动。三是乘子法，它是外部罚函数法的一种改进方法。其惩罚方式是在约束问题的Lagrange函数中加入相应的惩罚，这样既能保证迭代点会收敛到约束问题的极小点，更重要的是能保证数值计算的稳定性。本节首先讨论外部罚函数法。1.算法的构成首先讨论一个例子。求解（4.68）如图所示。此问题的容许集是直线图解法或Lagrange乘子法不难求出它的极小点是.。用根据前面提出的惩罚策略，即对容许点不予“惩罚”，而对非容许点则给予正无穷大的“惩罚”，设法将约束问题（4.68）转化为无约束问题。

（4.69）

那么无约束问题与（4.68）等价。问题是的特性太坏，无法用第3章讲过的任何一种无约束方法求解它。考虑“相近”函数（4.70）其中是任意给定的正数。是可微函数，所以可以用第3章讲的无约束方法求解它。求解以（4.70）为目标函数的无约束问题，其（解析）最优解

虽然不是（4.68）的容许点，但随着的增大，有。综上所述，为了求解约束问题（4.67），可以采用取如下的惩罚策略：给目标函数加上由约束函数构造的惩罚项。惩罚项要具备两个特点：ⅰ）包含有取值越来越大的正因子；

ⅱ）对于容许点，惩罚项取值为零；对于非容许点，惩罚项取值为正。以下讨论一般情况。对于仅含有等式约束的问题（4.71）可以采取如下的惩罚策略（4.72）仿照上述分析，对于仅含有不等式约束的问题（4.73）可采取的惩罚策略为（4.74）其中是阶跃函数，即（4.75）于是

进而是（4.73）的容许集。此式说明（4.74）符合前面拟订的惩罚策略。

其中

最后，对于同时具有等式约束和不等式约束的一般约束问题（4.67），可采取如下的惩罚策略（4.76)其中（4.77）称为约束问题(4.67)的罚函数。显然有（4.78）这里的是（4.67）的容许集。此外，把称为约束问题（4.67）的增广目标称为罚因子，称为惩罚项。函数，其中的于是，由约束最优化问题（4.67）引出如下的无约束最优化问题（4.79）定理4.22将指出，当固定时，无约束问题（4.79）的极小点有可能是约束问题（4.67）的极小点。定理4.22

对于某个给定的，若是无约束问题也是约束问题（4.67）的极小点恰是（4.67）的容许点。（4.79）的极小点，则的充要条件是证

必要性是显然的。因为极小点是容许点。充分性

设，这里的是约束问题（4.67）的容许集。那么对于，总有所以也是约束问题（4.67）的极小点。在实际的算法中，取为一个趋于正无穷大的正数，并对依次求解无约束问题把该定理说明,若由无约束问题(4.79)解出的极小点属于（4.67）的容许集，则它就是约束问题（4.67）的一般不属于。而若则就一定不是约束问题（4.67）的极小点。这时，应该，再重新求解无约束问题（4.79），新的极小点极小点。这时只需求解一次无约束问题。但实际上，这种有利的情况很少发生，即，增大向容许集进一步靠近，即向（4.67）的极小点进一步靠近。将序列即（4.80)由此得到极小点序列

。在4.6.2中将证明，如果这个序列收敛，则必收敛于约束问题（4.67）的极小点

约束问题（4.67）的方法称为外部罚函数法或外点法。。这种通过求解一系列无约束问题（4.80）而达到求解无像这样，通过求解一系列无约束最优化问题来求解约束最优问题的方法称为序列无约束极小化技术（SequentialUnconstrainedMinimizationTechnique，简记为SUMT）。算法4.6(外部罚函数法)P269算法说明：例4.12

用外部罚函数法求解(1)(2)

2.收敛性引理4.23

对于由算法4.6所产生的序列，总有（4.82）（4.83）（4.84）定理4.24

设和

都是

上的连续函数，则由算法4.6所产生的序列的任一聚点必是约束问题（4.67）的极小点。4.7内部罚函数法外部罚函数法所产生的迭代点一般不是容许点，所以往往只是近似地满足约束条件，这样的结果对于那些要求严格满足约束条件的实际问题是无法接受的。此外，对于有些约束问题，其目标函数在容许集外可能无定义，因此也无法使用外部罚函数法。为保证迭代点总是容许点，可以采用如下的内部罚函数法。1.算法的构成内部罚函数法的初始点必须是容许点，迭代点在容许集的内部移动。基本想法是，对越接近容许集边界的（容许）点施加越大的惩罚，对边界上的点干脆施加无穷大的惩罚。这好比在容许集的边界上筑就了一道高墙，阻碍迭代点穿越边界，把迭代点封闭在容许集内。根据这个想法，内部罚函数法就仅适用于具有不等式约束的问题，而且容许集的内点集合必须是非空集合；否则，会因为容许点全被加上无穷大的惩罚而失去惩罚的意义。考虑不等式约束问题（4.94）构造如下的增广目标函数就可以实现上面的想法。设（4.95）其中（4.96）称为障碍函数；仍称为罚因子；惩罚项。若

称为是（4.94）的容许集的内点，则惩罚函数的值是有限的正数；当由内部接近边界时，则至少有一个约束函数，例如第个，将趋于零，

于是必将趋于正无穷大。这正符合上述的惩罚思想。

现在固定,求解以(4.95)为目标函数的无约束问题（4.97）如果把初始点取为容许集的内点，按照的结构和无内，。约束下降迭代算法的特性，那么迭代点必将都在因此最后求得的极小点也必将属于例如，对于约束问题构造如下的增广目标函数书上图4-21画出了在容许集上目标函数

和惩罚项以及由这两者合成的增广目标函数

的曲线。这里，（在容许集内）的极小点我们通过求导数的方法获得。令由此解出最优解从书上图4-21容易看出，原约束问题的极小点是而增广目标函数的极小点是。这个例子说明，对于固定的

，无约束问题（4.97）的极小点一般不是约束则。这个结论具有一般性。

问题（4.94）的极小点。但是这个例子显示，若令，在实际的算法中，把取为一个趋于零的正数序列,求解一系列无约束问题,即对,依次求解（4.98）

由此得到极小点序列。在4.7.2中将证明，这个序列若收敛，则必收敛于约束问题（4.94）的极小点。这种通过求解一系列无约束问题（4.98）而达到求解约束问题（4.94）的方法称为内部罚函数法或内点法。障碍函数除（4.96）外还可以取为其中由（4.75）定义。算法4.7（内部罚函数法）

P277几点说明：例4.14

用内部罚函数法求解其中是非负常数。例4.15

用内部罚函数法求解解

增广目标函数为令于是，问题的最优解为2.收敛性引理4.25对于由算法4.7所产生的序列，总有（4.99）（4.100）

（4.101）

其中。定理4.26

设都是上的连续函数，的任一聚点必是约束问题则由算法4.7所产生的序列（4.94）的极小点。由于内部罚函数法不能处理等式约束，且寻求初始容许点的计算量往往太大。因此在实际计算中，人们往往将内部罚函数与外部罚函数法结合起来，形成所谓的混合罚函数法。4.8乘子法乘子法是针对外部罚函数法的一种改进方法。由于外部罚函数法随着罚因子的增大，增广目标函数的Hesse矩阵条件数变得越来越坏，从而导致在实际计算中，数值计算的稳定性变得越来越差，难以精确求解。乘子法是在约束问题的lagrange函数中加入相应的惩罚，使得在求解系列无约束问题时，罚因子不必趋于无穷大就能求到约束问题的最优解，而且数值计算的稳定性也能得到很好的保证。理论与计算实践皆表明，乘子法优于外部罚函数法。1.等式约束的情形首先介绍Hesternes（1969）乘子法，简称H乘子法。考虑等式约束问题（4.71），将其写成向量形式为（4.109）其中都是二次连续可微函数。设。（4.109）的Lagrange函数是（4.110）设是（4.109）的极小点，是相应的Lagrange乘子。根据定理4.1，则有（4.111）（4.112）注意到，对于，都有，因此由此可见，（4.109）与如下约束问题等价（4.113）这说明可以通过求解（4.113）达到求解（4.109）的目的。对（4.113）使用外部罚函数法，其增广目标函数为（4.114）应该注意到，其实是未知向量，所以实际上不能求出的极小点。下面将指出，在求的同时，采用.这就是乘子法的基本思想。迭代的方法也可以同时求出该法也因此而得名。实际上，用乘子法求解（4.109）时的增广目标函数是（4.115）这个函数比（4.72）具有更好的性质。首先证明一个引理。引理4.27设是对称矩阵，是矩阵。的非零向量都使得那么必存在非负数，当时，使得矩阵在上皆正定。如果所有满足，定理4.28

在约束问题(4.109)中，如果最优解和Lagrange乘子满足由定理4.2给出的，当时，使得也是的严格局部极小点。件，那么就存在非负数二阶充分条该定理表明，对（4.113）使用外部罚函数法时，只要罚因子不小于某个潜在的非负数，那么

（局部）极小点就有可能是（4.109）的（局部）极小点。的现在来求解以（4.115）为目标函数的无约束极小化问题（4.121）下面的定理将指出（4.109）与（4.121）的关系。定理4.29

设对于给定的参数和，是(4.121)的是（4.109）的最优解，且为相应的的充要条件是，即。最优解。那么Lagrange乘子向量定理4.29结合定理4.28说明：如果参数恰好取为了，又取了，然后求解（4.121）得出的最优解有恰好是（4.109）的容许点，那么就必是（4.109）的最优解。在实际计算中，是通过迭代的方式获得的。其迭代公式推导如下：对于给定的，设是（4.121），即（4.123）的极小点，那么利用（4.119），应有（4.124）另一方面，在（4.109）的最优点处，根据（4.111），应有（4.125）若设是列满秩矩阵，则使用最小二乘法，由上式可求出（参看推论3.17）。若，则当充分大时，也将是列满秩矩阵。于是，再次使用最小二乘法，由（4.124）又可得比较以上两式可知，当时，。因此，有理由采用如下的迭代公式求，即定理4.29实际上还给出了H乘子法的终止准则，即当充分小时，迭代终止。而一旦在迭代中

不收敛不够大，后，再迭代。收敛的快慢可用比值或收敛的太慢，根据定理4.28可知，这表明因此增大来度量。

算法4.8(等式约束问题的H乘子法)P285例4.16

用H乘子法求解等式约束问题（4.68）。解

增广目标函数为令由此解出（4.126）把换为，再把和的表达式代入下式，得到乘子迭代公式由此看到，只要，序列{}就收敛，而且越大，，上式两边取的极限，就有收敛越快。因此，对于任意给定的正数由此解出。把代到（4.126），即得最优解。从（4.127）的计算结果可以看出，与的取值无的取值保证{}收敛。这很容易理解。关，只要求因为若不然的话，就会有无数个Lagrange乘子，而这显然是不可能的。下面再简单介绍Powell(1969)乘子法，简称P乘子法。

Powell乘子法与H乘子法相比，唯一的差别在于它对每一个约束使用了不同的罚因子，亦即处罚因“人”而异。理论推导过程与H乘子法的相似，这里从略。Powell乘子法的增广目标函数为（4.128）算法4.9（等式约束问题的P乘子法）

P286计算实践表明，P乘子法比H乘子法效果好。2.不等式约束的情形这里将要介绍的是Rockafellar（1973）乘子法，它是把H乘子法巧妙地用到不等式约束问题上去而得到的求解仅含不等式约束问题（4.73）的一种方法。考虑不等式约束问题（4.129）引入辅助变量，把（4.129）转化为与其等价的等式约束问题（4.130）这时，可使用前述H乘子法求解（4.130），其增广目标函数为（4.131)求的极小。由于变量独立，所以求的极小可分步进行，即实际上，关于的极小可以用显示表出。因此，将（4.129）的增广目标函数定义为（4.132）

用解析法求解（4.132）