《惩罚函数法》PPT课件

《《惩罚函数法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、惩罚函数法（PenaltyFunctionMehthod）南京邮电大学理学院信息与计算科学系minf(x)s.t.s1(x)≥0……sm(x)≥0h1(x)=0……hn(x)=0数学模型将这种约束问题转化为无约束问题（罚函数法等）求解约束问题的方法分类直接从这种约束问题出发来求解。因无约束问题已有较好的求解方法比如BFGS,DFP将约束条件对问题的限制作用按一定的规则转换到目标函数上，然后对转换后得到的新的无约束问题求解,然后将求解的结果反映到原问题.仿照无约束优化问题的求解思想，构造“下降迭代算法”但

2、是构造的方向满足下降要求前，首先要满足可行域！所以这类方法我们称为可行下降方向法。minx12+x22s.t.x1+x2-2=0由图解法易见最优解为(1,1)T直观引例将这个问题改造为一个无约束问题如下：min(x12+x22)+(x1+x2-2)2(*)分析：任意点x若不满足原问题的约束，则(*)第二项就会非常大那么该点x就不会是(*)的最优解。这样的存在迫使最优解在可行域内取得。随着的增大或更特殊地取为+∞，则问题(*)就成为：min(x12+x22)当(x1+x2-2)=0.这恰为所要求解的原

3、问题.minx12+x22s.t.x1+x2-2=0为一个充分大的正的参数引例求解思想的理论支持问题min(x12+x22)+(x1+x2-2)2最优解的解析式为：问题“粗放”想法的进一步深入分析的最优解即是原问题的最优解，但是为+∞在计算机上无法实现。理论上特殊地取为+∞，则min(x12+x22)+(x1+x2-2)2(*)为一个较大的正的参数实际上充分大时，(*)的最优解即可为原问题的最优解。先给定，求解问题min(x12+x22)+(x1+x2-2)2.判断得到的点是否是原问题

4、的解，若还不是，则增大再求上述问题，若还不是，继续。比如本例：取为0,1,10,100,1000时的解如图,趋于(1,1)T.引例的计算机处理方法引例的计算机处理方法一般地，对于等式约束问题，minf(x)s.t.hj(x)=0,j=1:n将此问题改造成一个新问题(**)：～x～x这个新问题的最优解必定使得hj()接近于0引例求解思想推广到一般的等式约束问题因为使得hj(x)=0的那些x就能使得F(x,)的值比F(,）小～x现在的这个点就不会是这个无约束问题的极小点～x否则的话式子中的第二项就会是一

5、个很大的正数新目标函数的特征：在任意原问题的可行点x’处：F(x’,)=f(x’);在任意原问题的不可行点x”处：F(x”,)=f(x”)+大正数。根据这样的原则，对不等式约束问题可以类似构造：minf(x)s.t.si(x)≥0,i=1;m转化为(易验证满足上述原则)不等式约束问题改造为相应无约束优化问题的方法·x0转换原则的解释在极小化新无约束问题时所考虑的是整个空间上的点，而这些点其实是两大块：原可行域D和Rn-D当任取一点x0时F(x0,)显然是要比F(x,)(xD)大的，所以minF(

6、x,)时总体上就是从D外边向D里边(或是边界)“跑”！比如一个具体的例子：min(x-1)2s.t.x-2≥0构造F(x,)=(x-1)2+[max(0,-(x-2)]2取0,1,10时F的极小点如图总体上就是从D外边向D里边(或是边界)“跑”！对于混合约束问题minf(x)s.t.si(x)≥0,i=1:mhj(x)=0,j=1:n.也可以转化为混合约束问题改造为相应无约束优化问题的方法P(x)-----惩罚函数（惩罚项）----罚因子F(x,)-----增广目标函数给定初始点x(0)，初始惩

7、罚因子1，放大系数c>1,置k=1STEP1:以x(k-1)为初始点求解minF(x,k),得极小点x(k)STEP2:若x(k)符合原问题的最优解要求，stopSTEP3:k+1=c·k,置k=k+1转(i)外部罚函数法初步框架Proof(必要性)显然(充分性)若x是原问题的极小点,则对于原问题的任意容许点x,总有f(x)=F(x,)(∵在x处罚项=0)≤F(x,)(∵x是F的极小点)=f(x)(∵在x处罚项=0)这就说明x是原约束问题的最优解。定理(外部罚函数法的终止准则)无约束

8、问题F(x,)的极小点x恰是原约束问题的极小点的充要条件是x是原约束问题的可行点。解minF(x,k)=f(x)+罚项，得解x(k),要看它是否是容许点,而这只要看是否罚项<,若是，则x(k)就是原约束问题的一个好的近似解.所谓“符合要求”可作如下的解释：外部罚函数法给定初始点x(0)，初始惩罚因子1，放大系数c>1,>0,置k：=1STEP1:以x(k-1)为初始点求解minF(x,k)得极小点