07第三章罚函数法及改进算法

1、第3章 罚函数法及改进算法第3章 罚函数法及改进算法3.1 引言罚函数法是解决约束优化问题的重要方法，它的基本思想是用无约束问题代替约束问题，因而无约束问题的目标函数必须是原来的目标函数与约束函数的某种组合，类似线性规划中的M法求初始可行解，在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，所以称为罚函数法。这样把约束问题转化成求解一系列的无约束极小点，通过有关的无约束问题来研究约束极值问题，从而使问题变的简单。许多非线性约束优化方法都要用罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，不同的罚项对算法影响很大，根据罚项的不同可以分为

2、以下几类：外罚函数法对于问题 (3-1) (3-2) (3-3)其中为线性连续函数。定义外罚函数为: (3-4) (3-5)通常取，这样定义的外罚函数法，当为可行点是，；当不是可行点时，。而且离可行域越远的值越大，它优点是允许从可行域的外部逐步逼近最优点，但其明显的缺点是它需要求解一系列无约束极小化问题，计算工作量很大，且由于其收敛速度仅是线性的，往往需要较长的时间才能找到问题的近似解，再考虑到实际中所使用的终止准则，若实现不当，则算法很难找到约束问题的一个较好可行解，从而不适用于那些要求严格可行性的问题。内罚函数法它是针对不等式约束(3-1)(3-3)提出的，基本思想是在约束区域的边界筑起一

3、道“墙”来，当迭代点靠近边界时，函数值陡然增大，于是最优点被挡在可行域内部，这样产生的点列每个点都是可行点。通常定义内罚函数为： (3-6) (3-7)要减弱的影响，故令逐渐增大。内罚函数法的好处是每次迭代的点都是可行点，当迭代到一定阶段时，可以被接受为一个较好的近似最优解。但是内点罚函数法要求初始点位于可行域的内部，除特殊情况外，确定这样一个初始点并非易事。此外，由于内点罚函数不是处处有定义或不一定存在全局极小，故无约束最优化问题中的线性搜索方法不再适用，另外，当接近可行域边界时，内点罚函数法必须修正通常的线性搜索方法。 由于内点罚函数法不能处理等式约束，且寻求初始可行点的计算工作量往往太大

4、。因此，在实际中，为了求解一般的非线性约束优化问题，人们往往将内点罚函数法与外点罚函数法结合起来适用。混合罚函数法混合罚函数法是针对问题(3-1)-(3-3)提出来的，当初始点给定后，对等式约束和不被满足的那些不等式约束用外罚函数法，而被满足的那些不等式约束用内罚函数法。通常定义混合罚函数为：(3-8) (3-9)精确罚函数法对于外点罚函数法和内点罚函数法来说，其工作量很大，收敛慢的主要原因是它们需要求解一系列的无约束优化问题，而导致相应罚函数的无约束极小化运算越来越难于精确执行，效率差则是因为需要罚因子趋于无穷大或零所带来的罚函数呈病态问题。由此自然想到，能否设计出一种罚函数，使得只要令其中

5、的罚参数取适当的有限值后，该罚函数的无约束极小点就恰好是原约束问题的最优解，从而克服外、内点罚函数法的缺点呢？通常称这样的罚函数为精确罚函数。对问题(3-1)-(3-3)，定义如下，对于罚函数其中是罚因子。如果则在二阶充分条件，的假定下可证是罚函数的局部严格极小点。所以罚函数也常称为精确罚函数。同理，罚函数也是精确罚函数。乘子罚函数法内外罚函数法的缺点是需要罚因子趋于无穷大才能使求解罚函数的极小和求解原向题等价。乘子罚函数法具有不要求初始点为严格内点，甚至不要求其为可行点的特点，它利用近似Lagrange乘子，求其近似解，并且逼近最优解，而不需要无穷大的罚因子，因此对它的研究有重要的理论和实用

6、价值。最早的乘子罚函数(又称为增广Lagrange函数)是由Henstenes(1969)针对等式约束问题(3-1)(3-2)导出的，其形式为: (3-10)增广Lagrange函数的另一种等价形式是在1969年由Powell提出的，它提出对进行平移，即用代替，是参数，这种平移的好处是不破坏的方向，由此Powell(1969)得到罚函数: (3-11)如果定义，则知式(3-10)与(3-11)只相差与无关的项，由于式(3-10)与(3-11)等价，故罚函数(3-10)也称为Henstenes-Powell罚函数。我们看到通常都是用二次罚函数作为罚项，因此称之为二次罚函数乘子法。然而，它的缺点是

7、容易引起罚因子过大，造成罚函数的Hesse矩阵严重病态。许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，因此对不同罚项的研究具有重要的理论和实际价值。近年来，许多研究者试图通过改变罚项构造出新的罚函数，有效地避免罚因子过大引起的罚函数的Hesse矩阵严重病态的情况。3.2 优化中的罚函数法对一般约束最优化问题 (3-12) (3-13) (3-14)定义1 称 (3-15)为问题(3-12)-(3-14)的优化罚函数，为罚因子，其中罚项 (3-16)其中且满足如下性质：(1) 在中连续可微且为对称凸函数；(2) 对，；当且仅当时

8、，；(3) ，。若定义 则是可行点当且仅当。我们通过的极小点(其中为一定值)，得到相应无约束极小点，序列来逼近约束问题(3-12)-(3-14)的极小点。罚函数算法：步1 选定初始点为；选取初始惩罚因子(可取)，惩罚因子的放大系数(可取)；置。步2 以为初始点，求解无约束问题，其中，设其极小点为。步3 若，则就是所要求的最优解，停止；否则转下一步。步4 置；，转步2。由罚项的特点，当趋向于无穷时，随着的不断增大，对每个不可行点的惩罚也不断增大并趋向于无穷。因此，在对应于的无约束极小化问题的最优解处，的值应不断减小，从而保证逐步趋于可行并最终达到问题(3-12)-(3-14)的最优解。由，的定义

9、及极小点的含义，我们很容易证明下列结论。引理1 给定，是(3-15)的解，则也是约束问题 (3-17) (3-18)的解，其中。证明 由的性质知在是增函数，且 ，又因为为对称函数，所以，由此可得对任何满足式(3-18)，由的定义，我们有 (3-19)所以 (3-20)故知是问题(3-17)-(3-18)的解。证毕。 由以上引理可知，若取充分小，则当算法迭代结束时，是问题(3-12)- (3-14)的近似解。引理2 对于由算法所产生的序列总有， (3-21) (3-22) (3-23)其中。证明 由和可知，又因为是的极小点，所以对于任意总有，特别有。由此可证得(3-21)。因为和分别使和取极小，

10、所以有由上式可得由此可得由于，所以(3-22)成立。最后，由式(3-21)和(3-22)得式(3-23)成立。证毕。定理1 设非线性约束问题(3-12)-(3-14)的最优解存在，设由算法产生，且罚参数序列单调递增且趋于，则的任何极限点都是问题(3-12)-(3-14)的可行域上的最优解。证明 设，又设是问题(3-12)-(3-14)的最优解，由于是无约束问题 的解，由于可行，即，故有即由此可得，由于，。故得，且。即可行，且，但是问题(3-12)-(3-14)的解，因此也是问题(3-12)-(3-14)的解。 证毕。 我们现在对于优化中的罚函数法进行一般类型的概况，并证明其收敛性，但是需要说明

11、的是其中不同种类的罚函数法在其收敛速度各有其不同。3.3 改进的罚函数法及收敛性3.3.1 改进的罚函数算法罚函数法是解决约束优化问题的重要方法，它的基本思想是把约束优化问题转化成求解一系列的无约束极小化问题。通过有关的无约束问题来研究约束极值问题，经常采用的方法之一是在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，这种方法称为罚函数法。如何选取罚函数，以加速迭代算法的收敛速度，一直是约束优化问题研究的热点问题。罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要作用，不同罚项的选取，构成不同的罚函数，必然会对算法产生不同的影响，因此对不同罚项

12、的研究具有重要的理论和实用价值。对一般约束最优化问题 (3-24) (3-25) (3-26)通常使用的外函数形式为：其中罚项为：，。为参数，若取，我们称上述罚函数为二次罚函数。问题(3-24)-(3-26)的可行域为显然，当为可行点时，；当不是可行点时，而且离可行域越远的值越大。它的优点是允许从可行域的外部逐步逼近逼近最优点，但按上述定义的罚函数的缺点是：需要罚因子趋于无穷大，才可能使求解罚函数的极小和求解原问题等价。为了有效的改善这种罚函数，我们试图构造一种能够加速迭代算法收敛的外罚函数法。本文提出一种用双曲正弦函数作罚项的罚函数，并由此构建了双曲正弦罚函数法，不仅证明了该罚函数和算法的合

13、理性及迭代点列的收敛性，而且做了数值实验。结果表明本文中所提出的罚函数及对应的算法可以在罚因子与二次罚函数方法中的罚因子相同的情况下，有着更快的收敛速度。定义1 称 (3-27)为问题(3-24)-(3-26)的双曲正弦罚函数，为罚因子，其中罚项 (3-28)其中，；，。若定义 则是可行点当且仅当。我们通过一系列双曲正弦函数的极小点，其中为一定值，得到相应无约束极小点，序列来逼近约束问题(3-24)-(3-26)的极小点。双曲正弦罚函数算法：步1 选定初始点为；选取初始惩罚因子(可取)，惩罚因子的放大系数(可取)；置。步2 以为初始点，求解无约束问题其中设其极小点为。步3 若，则就是所要求的最

14、优解，停止；否则转下一步。步4 置；，转步2。3.3.2 收敛性证明及数值试验引理1 设函数和由定义1定义，由算法产生，且罚参数序列单调递增，则 证明 由的定义知上面的两式相加，得因此，即成立。 由得即成立。 由以及的定义得即成立。 证毕。引理2 设函数和由定义1定义，由算法产生，且罚参数序列单调递增，记，则也是约束问题 (3-29) 的解。证明 设是问题(3-29)的可行点，我们有因此是问题(3-29)的解。 证毕。定理1 设非线性约束问题(3-24)-(3-26)的最优解存在，设由算法产生，且罚参数序列单调递增且趋于，则的任何极限点都是问题(3-24)-(3-26)的可行域上的最优解。证明

15、 设，又设是问题(3-24)-(3-26)的最优解，由于是无约束问题，的解，由于可行，即，故有即由此可得，由于，。故得，且。即可行，且，但是问题(3-24)-(3-26)的解，因此也是问题(3-24)-(3-26)的解。证毕。我们通过数值实验来检验本算法的有效性 在以下“次数”的是求解相应无约束问题的次数，“”和“”分别表示双曲正弦罚函数法和二次罚函数法。是程序结束时所取罚因子，用matlab编程实现。表3-1 两种方法的数值比较：Table 3-1 the numerical comparison of the two methods方法初始点算法中罚因子次数最优解(-1,1)201(0.2500,0.7500)36(0.2499,0.7501)(-5,10)203(0.2500,0.7500)34(0.2500,0.7500)(10,1,-5)247(-0.4999,-0.5004,-0.4999)244(-0.5000,-0.5001,-0.5001)(