罚函数法及改进算法.docx

第3章罚函数法及改进算法引言罚函数法是解决约束优化问题的重要方法，它的基本思想是用无约束问题代替约束问题，因而无约束问题的目标函数必须是原来的目标函数与约束函数的某种组合，类似线性规划中的M法求初始可行解，在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，所以称为罚函数法这样把约束问题转化成求解一系列的无约束极小点，通过有关的无约束问题来研究约束极值问题，从而使问题变的简单许多非线性约束优化方法都要用罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，不同的罚项对算法影响很大，根据罚项的不同可以分为以下几类：外罚函数法对于问题minf(x)(3-1)s.tCi(x)0i1,2,,m;(3-2)Ci(x)0im1,m2,,n;(3-3)其中f:RnR为线性连续函数定义外罚函数为：L(x,)f(x)P(x)f(x)Q(x)(3-4)mnQ(x)Ci(x)min{0,G(x)}(3-5)i1im1通常取==2,这样定义的外罚函数法，当x为可行点是，Q(x)0;当x不是可行点时，Q(x)0而且x离可行域越远Q(x)的值越大，它优点是允许从可行域的外部逐步逼近最优点，但其明显的缺点是它需要求解一系列无约束极小化问题，计算工作量很大，且由于其收敛速度仅是线性的，往往需要较长的时间才能找到问题的近似解，再考虑到实际中所使用的终止准则，若实现不当，则算法很难找到约束问题的一个较好可行解，从而不适用于那些要求严格可行性的问题。

内罚函数法它是针对不等式约束(3-1)(3-3)提出的，基本思想是在约束区域的边界筑起一道“墙”来，当迭代点靠近边界时，函数值陡然增大，于是最优点被挡在可行域内部，这样产生的点列Xk每个点都是可行点通常定义内罚函数为：，1-，…B(x,)f(x)—B(x)(3-6)—m1B(x)(3-7)iiC(x)|要减弱B(x)的影响，故令逐渐增大内罚函数法的好处是每次迭代的点都是可行点，当迭代到一定阶段时，可以被接受为一个较好的近似最优解但是内点罚函数法要求初始点位于可行域的内部，除特殊情况外，确定这样一个初始点并非易事止匕外，由于内点罚函数不是处处有定义或不一定存在全局极小，故无约束最优化问题中的线性搜索方法不再适用，另外，当接近可行域边界时，内点罚函数法必须修正通常的线性搜索方法由于内点罚函数法不能处理等式约束，且寻求初始可行点的计算工作量往往太大因此，在实际中，为了求解一般的非线性约束优化问题，人们往往将内点罚函数法与外点罚函数法结合起来适用混合罚函数法混合罚函数法是针对问题(3-1)-(3-3赛出来的，当初始点xo给定后，对等式约束和不被飞满足的那些不等式约束用外罚函数法，而被xo满足的那些不等式约束用内罚函数法。

通常定义混合罚函数为：__11P(x,)f(x)-(―)P(x)(3-8)iI1q(x)—22，一一、P(x)G(x)min{0,c(x)}(3-9)1 1i%11 {iG(x)0,im1,m2,L,n}12 {iq(x)0,im1,m2,L,n}精确罚函数法对于外点罚函数法和内点罚函数法来说，其工作量很大，收敛慢的主要原因是它们需要求解一系列的无约束优化问题，而导致相应罚函数的无约束极小化运算越来越难于精确执行，效率差则是因为需要罚因子趋于无穷大或零所带来的罚函数呈病态问题由此自然想到，能否设计出一种罚函数，使得只要令其中的罚参数取适当的有限值后，该罚函数的无约束极小点就恰好是原约束问题的最优解，从而克服外、内点罚函数法的缺点呢通常称这样的罚函数为精确罚函数对问题(3-1)-(3-3),定义C()(x)(G()(x),LCm()(x))T如下Ci()(x)Ci(x),i1,2,,mc()(x)min{0,G(x)},im1,m2,,n对于L1罚函数P(x)f(x)|c()(x)|1其中0是罚因子如果III则在二阶充分条件dTWd0,d0,ATd0的假定下可证x是L1罚函数的局部严格极小点。

所以L罚函数也常称为L1精确罚函数同理，L罚函数P(x)f(x)|C()(x)|也是精确罚函数乘子罚函数法内外罚函数法的缺点是需要罚因子趋于无穷大才能使求解罚函数的极小和求解原向题等价乘子罚函数法具有不要求初始点为严格内点，甚至不要求其为可行点的特点，它利用近似Lagrange乘子，求其近似解，并且逼近最优解，而不需要无穷大的罚因子，因此对它的研究有重要的理论和实用价值最早的乘子罚函数(又称为增广Lagrange函数)是由Henstenes(1969)十对等式约束问题(3-1)(3-2加出的，具形式为：P(x,,)f(x)Tc(x)y|C(X)||2(3-10)增广Lagrange函数的另一种等价形式是在1969年由Powell提出的，它提出对q(x)进行平移，即用G(x)i代替G(x),i是参数，这种平移的好处是不破坏ci(x)的方向，由此Powell(1969*1至I罚函数：m——T2P(x,,)f(x)c(x)-(Ci(x)i)(3-11)2i1m如果定义ii,则知式(3-10)与(3-11)只相差与x无关的项一i2,2i1由于式(3-10)与(3-11)等价，故罚函数(3-10)也称为Henstenes-Powell罚函数。

我们看到通常都是用二次罚函数作为罚项，因此称之为二次罚函数乘子法然而，它的缺点是容易引起罚因子过大，造成罚函数的Hesse矩阵严重病态许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个点的好坏，这在选择新点确定步长等方面都起着重要的作用，因此对不同罚项的研究具有重要的理论和实际价值近年来，许多研究者试图通过改变罚项构造出新的罚函数，有效地避免罚因子过大引起的罚函数的Hesse矩阵严重病态的情况优化中的罚函数法对一般约束最优化问题minf(x)s.tci (x) 0ci (x) 01,2, , m;m 1,m 2, ,n;(3-13)(3-14)定义 1 称L(x,k) f(x)为问题 (3-12)-(3-14)的优化罚函数，mQ(x) [q(ci (x))]i1(x) f(x) kQ(x)0 为罚因子，其中罚项n{ q(min[0, ci(x)])} im1(3-15)(3-16)q(t)其中tR且满足如下性质：(1)q(t)在R中连续可微且为对称凸函数;(2) 对 t R，q(t) 0；当且仅当 t0 时，q(t) 0；(3) tlim q(t)tlim q(t)若定义~ci (x)ci(x)min[0, ci(x)]1,2,L ,mm 1,m 2,L ,n则x是可行点当且仅当ci(x)0。

k 为一定值 )， 得到相应无约束极小点，*x1 0 (可取 1 1 )，惩罚因我们通过L(x,k)的极小点(其中序列xk来逼近约束问题(3-12)-(3-14)的极小点罚函数算法：步1选定初始点为x0；选取初始惩罚因子子的放大系数c1(可取c10)；置k1步2以xk1为初始点，求解无约束问题minL(x,k)，xRn其中L(x,k)f(x)Pk(x)f(x)kQ(x),设其极小点为Xk步3若kQ(x),则xk就是所要求的最优解，停止；否则转下一步步4置k1ck；kk1，转步2由罚项的特点，当k趋向于无穷时，随着k的不断增大，对每个不可行点的惩罚kQ(x)也不断增大并趋向于无穷因此，在对应于k的无约束极小化问题的最优解xk处，kQ(x)的值应不断减小，从而保证xk逐步趋于可行并最终达到问题(3-12)-(3-14)的最优解由Q(x),L(x,k)的定义及极小点的含义，我们很容易证明下列结论引理1给定k0，xk是(3-15)的解，则xk也是约束问题minnf(x)(3-17)xRs.t|ci(x)|ii1,2,L,n(3-18)~的解，其中i|ci(xk)|~~证明由q(x)的性质知在(0,)是增函数，且q(|ci(xk)|)q(|ci(x)|)，~~~~又因为q(x)为对称函数，所以q(|ci(xk)|)q(ci(xk))，q(|ci(x)|)q(ci(x))，由此可得~~q(ci(xk))q(ci(x))对任何x满足式(3-18),由Xk的定义，我们有n~n~f(x)kq(ci(x))f(xk)kq(ci(xk))(3-19)i1i1所以n~~f(x)f(xk)k[q(ci(xk))q(ci(x))]f(xk)xk(3-20)i1故知Xk是问题(3-17)-(3-18)的解。

证毕由以上引理可知，若取充分小，则当算法迭代结束时，xk是问题(3-12)-(3-14)的近似解引理2对于由算法所产生的序列xk总有，L(xk1,k1)L(xk,k)(3-21)Q(xk1)Q(xk)(3-22)f(xk1)f(xk)(3-23)其中k1证明由L(x,)f(x)Q(x)和ki卜可知，L(Xki,ki)f(Xki)kiQ(Xki)f(Xki)kQ(Xki)L(Xki,k)又因为Xk是L(x,k)的极小点，所以对于任意X总有L(x,k)L(Xk,k),特别有L(xki,k)L(xk,k)O由此可证得(3-2i)因为Xk和Xki分别使L(x,k)和L(x,ki)取极小，所以有f(Xki)kQ(Xki)f(Xk)kQ(Xk)f(Xk)kiQ(Xk)f(Xki)kiQ(Xki)由上式可得f(Xki)f(Xk)k[Q(Xk)Q(Xki)]ki[Q(Xk)Q(Xki)]f(Xki)f(Xk)由此可得(kik)[Q(Xk)Q(Xki)]0由于kik0,所以(3-22)成立最后，由式(3-2i)和(3-22)得式(3-23)成立定理i设非线性约束问题(3-i2)-(3-i4)的最优解存在，设Xk由算法产生，且罚参数序列k单调递增且趋于，则xk的任何极限点都是问题(3-i2)-(3-i4)的可行域上的最优解。

一*.证明设Xkx,又设X是问题(3-i2)-(3-i4)的最优解，由于Xk是无约束问题minLk(x)xRn的斛，由于x可仃，即Q(x)0,故有*_*_*_*Lk(Xk)Lk(x)f(x)kQ(x)f(x)即___*Lk(Xk)f(Xk)kQ(Xk)f(x)*由此可得0Q(xJ-(^)一巴)，由于Xkx,k故得k_*_*f(x)f(x),且Q(x)00***即x可行，且f(x)f(x),但x是问题(3-12)-(3-14)的解，因此x也是问题(3-12)-(3-14)的解我们现在对于优化中的罚函数法进行一般类型的概况，并证明其收敛性，但是需要说明的是其中不同种类的罚函数法在其收敛速度各有其不同改进的罚函数法及收敛性改进的罚函数算法罚函数法是解决约束优化问题的重要方法，它的基本思想是把约束优化问题转化成求解一系列的无约束极小化问题通过有关的无约束问题来研究约束极值问题，经常采用的方法之一是在原来的目标函数上加上由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域，这种方法称为罚函数法如何选取罚函数，以加速迭代算法的收敛速度，一直是约束优化问题研。