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

第3章罚函数法及改进算法29第3章罚函数法及改进算法3.1引言罚函数法是解决约束优化问题的重要方法，它的基本思想是用无约束问题代替约束问题，因而无约束问题的目标函数必须是原来的目标函数与约束函数的某种组合，类似线性规划中的M法求初始可行解，在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，所以称为罚函数法。这样把约束问题转化成求解一系列的无约束极小点，通过有关的无约束问题来研究约束极值问题，从而使问题变的简单。许多非线性约束优化方法都要用罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，不同的罚项对算法影响很大，根据罚项的不同可以分为以下几类：外罚函数法对于问题min()fx(3-1).st()0icx1,2,,;im(3-2)()0icx1,2,,;immn(3-3)其中:nfRR为线性连续函数。定义外罚函数为:(,)Lx()()fxPx()()fxQx(3-4)()Qx11()min{0,()}mniiiimcxcx(3-5)通常取==2，这样定义的外罚函数法，当x为可行点是，()0Qx；当x不是可行点时，()0Qx。而且x离可行域越远()Qx的值越大，它优点是允许从可行域的外部逐步逼近最优点，但其明显的缺点是它需要求解一系列无燕山大学理学硕士毕业论文30约束极小化问题，计算工作量很大，且由于其收敛速度仅是线性的，往往需要较长的时间才能找到问题的近似解，再考虑到实际中所使用的终止准则，若实现不当，则算法很难找到约束问题的一个较好可行解，从而不适用于那些要求严格可行性的问题。内罚函数法它是针对不等式约束(3-1)(3-3)提出的，基本思想是在约束区域的边界筑起一道“墙”来，当迭代点靠近边界时，函数值陡然增大，于是最优点被挡在可行域内部，这样产生的点列kx每个点都是可行点。通常定义内罚函数为：1(,)()()BxfxBx(3-6)11()()miiBxcx(3-7)要减弱()Bx的影响，故令逐渐增大。内罚函数法的好处是每次迭代的点都是可行点，当迭代到一定阶段时，可以被接受为一个较好的近似最优解。但是内点罚函数法要求初始点位于可行域的内部，除特殊情况外，确定这样一个初始点并非易事。此外，由于内点罚函数不是处处有定义或不一定存在全局极小，故无约束最优化问题中的线性搜索方法不再适用，另外，当接近可行域边界时，内点罚函数法必须修正通常的线性搜索方法。由于内点罚函数法不能处理等式约束，且寻求初始可行点的计算工作量往往太大。因此，在实际中，为了求解一般的非线性约束优化问题，人们往往将内点罚函数法与外点罚函数法结合起来适用。混合罚函数法混合罚函数法是针对问题(3-1)-(3-3)提出来的，当初始点0x给定后，对等式约束和不被0x满足的那些不等式约束用外罚函数法，而被0x满足的那些不等式约束用内罚函数法。通常定义混合罚函数为：111(,)()()()()iIiPxfxPxcx(3-8)第3章罚函数法及改进算法312221()()min{0,()}miiiiIPxcxcx(3-9)1{()0,1,2,,}iIicximmn2{()0,1,2,,}iIicximmn精确罚函数法对于外点罚函数法和内点罚函数法来说，其工作量很大，收敛慢的主要原因是它们需要求解一系列的无约束优化问题，而导致相应罚函数的无约束极小化运算越来越难于精确执行，效率差则是因为需要罚因子趋于无穷大或零所带来的罚函数呈病态问题。由此自然想到，能否设计出一种罚函数，使得只要令其中的罚参数取适当的有限值后，该罚函数的无约束极小点就恰好是原约束问题的最优解，从而克服外、内点罚函数法的缺点呢？通常称这样的罚函数为精确罚函数。对问题(3-1)-(3-3)，定义()()()1()((),())TmCxcxcx如下()()()iicxcx，1,2,,im()()min{0,()}iicxcx，1,2,,immn对于1L罚函数()11()()()PxfxCx其中0是罚因子。如果则在二阶充分条件0TdWd，0d，0TAd的假定下可证x是1L罚函数的局部严格极小点。所以1L罚函数也常称为1L精确罚函数。同理，L罚函数()1()()()PxfxCx也是精确罚函数。乘子罚函数法内外罚函数法的缺点是需要罚因子趋于无穷大才能使求解罚函数的极小和求解原向题等价。乘子罚函数法具有不要求初始点为严格内点，甚至不燕山大学理学硕士毕业论文32要求其为可行点的特点，它利用近似Lagrange乘子，求其近似解，并且逼近最优解，而不需要无穷大的罚因子，因此对它的研究有重要的理论和实用价值。最早的乘子罚函数(又称为增广Lagrange函数)是由Henstenes(1969)针对等式约束问题(3-1)(3-2)导出的，其形式为:2(,,)()()()2TPxfxcxcx(3-10)增广Lagrange函数的另一种等价形式是在1969年由Powell提出的，它提出对()icx进行平移，即用()iicx代替()icx，i是参数，这种平移的好处是不破坏()icx的方向，由此Powell(1969)得到罚函数:21(,,)()()(())2mTiiiPxfxcxcx(3-11)如果定义ii，则知式(3-10)与(3-11)只相差与x无关的项212mii，由于式(3-10)与(3-11)等价，故罚函数(3-10)也称为Henstenes-Powell罚函数。我们看到通常都是用二次罚函数作为罚项，因此称之为二次罚函数乘子法。然而，它的缺点是容易引起罚因子过大，造成罚函数的Hesse矩阵严重病态。许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，因此对不同罚项的研究具有重要的理论和实际价值。近年来，许多研究者试图通过改变罚项构造出新的罚函数，有效地避免罚因子过大引起的罚函数的Hesse矩阵严重病态的情况。3.2优化中的罚函数法对一般约束最优化问题min()fx(3-12)第3章罚函数法及改进算法33.st()0icx1,2,,;im(3-13)()0icx1,2,,;immn(3-14)定义1称(,)kLx()()kfxPx()()kfxQx(3-15)为问题(3-12)-(3-14)的优化罚函数，0为罚因子，其中罚项11()[(())]{(min[0,()])}mniiiimQxqcxqcx(3-16)()qt其中tR且满足如下性质：(1)()qt在R中连续可微且为对称凸函数；(2)对tR，()0qt；当且仅当0t时，()0qt；(3)lim()tqt，lim()tqt。若定义~()()min[0,()]iiicxcxcx1,2,,1,2,,imimmn则x是可行点当且仅当()0icx。我们通过(,)kLx的极小点(其中k为一定值)，得到相应无约束极小点，序列kx来逼近约束问题(3-12)-(3-14)的极小点*x。罚函数算法：步1选定初始点为0x；选取初始惩罚因子10(可取11)，惩罚因子的放大系数1c(可取10c)；置1k。步2以1kx为初始点，求解无约束问题min(,)nkxRLx，其中(,)()()()()kkkLxfxPxfxQx，设其极小点为kx。步3若()kQx，则kx就是所要求的最优解，停止；否则转下一步。步4置1kkc；1kk，转步2。由罚项的特点，当k趋向于无穷时，随着k的不断增大，对每个不可行点的惩罚()kQx也不断增大并趋向于无穷。因此，在对应于k的无约束极小化问题的最优解kx处，()kQx的值应不断减小，从而保证kx逐步趋于可燕山大学理学硕士毕业论文34行并最终达到问题(3-12)-(3-14)的最优解。由()Qx，(,)kLx的定义及极小点的含义，我们很容易证明下列结论。引理1给定0k，kx是(3-15)的解，则kx也是约束问题min()nxRfx(3-17).st|()|iicx1,2,,in(3-18)的解，其中~|()|iikcx。证明由()qx的性质知在(0,)是增函数，且~~(|()|)(|()|)iikqcxqcx，又因为()qx为对称函数，所以~~(|()|)(())iikkqcxqcx，~~(|()|)(())iiqcxqcx，由此可得~~(())(())iikqcxqcx对任何x满足式(3-18)，由kx的定义，我们有~1()(())nikifxqcx~1()(())nikkkifxqcx(3-19)所以~~1()()[(())(())]()niikkkkkifxfxqcxqcxfxx(3-20)故知kx是问题(3-17)-(3-18)的解。证毕。由以上引理可知，若取充分小，则当算法迭代结束时，kx是问题(3-12)-(3-14)的近似解。引理2对于由算法所产生的序列kx总有，11(,)(,)kkkkLxLx(3-21)1()()kkQxQx(3-22)1()()kkfxfx(3-23)第3章罚函数法及改进算法35其中1k。证明由(,)()()LxfxQx和1kk可知，11111(,)()()kkkkkLxfxQx111()()(,)kkkkkfxQxLx又因为kx是(,)kLx的极小点，所以对于任意x总有(,)(,)kkkLxLx，特别有1(,)(,)kkkkLxLx。由此可证得(3-21)。因为kx和1kx分别使(,)kLx和1(,)kLx取极小，所以有11()()()()kkkkkkfxQxfxQx1111()()()()kkkkkkfxQxfxQx由上式可得11()()[()()]kkkkkfxfxQxQx111[()()]()()kkkkkQxQxfxfx由此可得11()[()()]0kkkkQxQx由于10kk，所以(3-22)成立。最后，由式(3-21)和(3-22)得式(3-23)成立。证毕。定理1设非线性约束问题(3-12)-(3-14)的最优解存在，设kx由算法产生，且罚参数序列k单调递增且趋于，则kx的任何极限点都是问题(3-12)-(3-14)的可行域上的最优解。证明设*kxx，又设*x是问题(3-12)-(3-14)的最优解，由于kx是无约束问题min()kLxnxR的解，由于*x可行，即*()0Qx，故有****()()()()()kkkkLxLxfxQxfx即*()()()()kkkkkLxfxQxfx燕山大学理学硕士毕业论文36由此可得*()()0()kkkfxfxQx，由于*kxx，k。故得**()()fxfx，且*()0Qx。即*x可行，且**()()fxfx，但*x是问题(3-12)-(3-14)的解，因此*x也是问题(3-12)-(3-14)的解。证毕。我们现在对于优化中的罚函数法进行一般类型的概况，并证明其收敛性，但是需要说明的是其中不同种类的罚函数法在其收敛速度各有其不同。3.3改进的罚函数法及收敛性3.3.1改进的罚函数算法罚函数法是解决约束优化问题的重要方法，它的基本思想是把约束优化问题转化成求解一系列的无约束极小化问题。通过有关的无约束问题来研究约束极值问题，经常采用的方法之一是在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近