罚函数法

邵建峰《运筹与优化》邵建峰第五章约束最优化方法信息与计算科学系邵建峰本章内容：5.1约束最优化问题的最优性条件5.2罚函数法5.3乘子(罚函数)法5.4投影梯度法5.5简约梯度法5.6约束变尺度法邵建峰7.1罚函数法信息与计算科学系邵建峰本节内容：一.外罚函数法二．内罚函数法约束最优化问题的罚函数思想：min()fxmixgi,,2,10)(ljxhj,,2,10)(nTnRxxxx),,,(21s.t.其可行（容许）解集|()0,1,2,,,()0,1,2,,,ijSxgximhxjlnTnRxxxx),,,(21约束优化问题的求解思想，一种常用的方法是将其转化为无约束问题.其中的约束转化为目标函数的一部分.满足约束时，对应的函数值很小;不满足约束时,对应的函数值很大——”惩罚”.在求解过程中,为使得总的目标函数值最小,得到的解一般会满足约束.这类方法一般称为罚函数法.此外，约束优化问题的求解方法还包括：可行方向法；投影梯度法；序列二次规划方法等等.一.外罚函数法min()fxmixgi,,2,10)(ljxhj,,2,10)(nTnRxxxx),,,(21s.t.D在约束集D的外部，我们给目标函数以一个较大的惩罚项，以让目标函数的最小值点向约束集D逼近，从而求得原问题的最优解。1、等式约束问题min()fxljxhj,,2,10)(s.t.例1求解约束优化问题221212min(,)fxxxx1220xxs.t.解:本问题就是求原点到直线x1+x2-2=0上的点的最短距离.显然最优解为(1,1)T.最优值为2.外罚函数法：设辅助函数为则以F(x1,x2)为目标函数的无约束问题的极小点必在直线x1+x2-2=0上,且目标函数的取值与原来问题的目标函数的取值一致.只是该函数的性质比较糟糕,无法用一般的算法求解.12(,)Fxx221212,2xxxx12,2xx外罚函数法：考虑下面的增广目标函数其中σ是很大的正数.以其为目标函数,解无约束问题,得到最优解为当σ→+∞时,有(x1(s),x2(s))T→(1,1)T=x*.即无约束问题最优解的极限为原问题最优解.注:辅助函数的目标函数值为在σ→+∞时也逼近于原问题的最优值2.12(,,)Pxx12221()()xx4212212xx2122()xx外罚函数法(等式约束问题)：构造如下增广目标函数：其中0为参数,称为罚因子.对于惩罚项当x为可行解时,当x不是可行解时,越大,惩罚越重.min()fx()0,1,2,,ihxils.t.1(,)()|()|,liiPxfxhx11()|()|:liiPxhx00(),(),(,)();ihxPxPxfx00(),(),ihxPx(,)()().PxfxPx外罚函数法(等式约束问题)：min()fx()0,1,2,,ihxils.t.当充分大时,要使P(x,)取极小值,在一定条件下,当→∞时,P(x,)的极小点逼近于原问题的解.(,)()()PxfxPx()Px应充分小,即P(x,)的极小点充分逼近可行域.2、不等式约束问题min()fx()0,1,2,,igxims.t.可以构造增广目标函数其中“惩罚项”的作用与等式约束时的情形类似.(,)()()PxfxPx10001()()|()|,(),,imiiigxPxgxgx10|min(,())|miigx12|()|()()miiigxgx例222212101(,)[min(,)]Pxxxx解问题是求点(0,0)T到半平面显然最优点为x*=(-1,0)T,最优值为f(x*)=1.设增广目标函数为求解约束优化问题221212min(,)fxxxx110xs.t.x≤-1的最短距离.故令得它是minP(x,σ)的最优解,最优值为当σ→+∞时,x1(σ)→-1,x2(σ)→0.因此22212101(,)[min(,)]Pxxxx22121222121110110,(),xxxxxxx111111212211,,(),Pxxxxxx222Pxx120,PPxx1201(),().xx221111(,)()()Pxx(σ)→x*,P(x,σ)→f(x*)=1.在上面的两个例子中,当→+∞时,P(x,)的最优解x()趋向于极限x*.而x*即为原约束问题的最优解.不过x()往往不满足约束条件,在迭代过程中,x()从可行域的外部逐步趋于原问题的最优解.因此上面的方法称为外罚函数法.通过一系列无约束最优化问题来求解约束最优化问题,称为序列无约束极小化方法(SequentialUnconstrainedMini-mizationTechnique),因此外罚函数法又称为SUMT外点法.3、一般约束优化问题可以构造增广目标函数其中求解原问题转化为求解一系列的无约束问题(,)()()PxfxPxmin()fxs.t.()0,1,2,,igxim()0,1,2,,jhxjl11()|min(0,())||()|(1,1)mlijijPxgxhx0称为罚因子.称为罚函数,()PxminP(x,k)(k→+∞)外罚函数法(算法步骤)：得最优解xk=x(k).Step1以xk-1为初始点解无约束问题取控制误差ε0,罚因子放大系数c1,初始点x0,初始罚因子1,令k=1.Step2判别是否满足：若是，则以xk为问题的近似最优解,否则,令k+1=ck,k=k+1,转Step1.min(,)()()kkPxfxPx(),kkPxStop;(),kkPx外罚函数法(收敛性质)：对SUMT外点法产生的点列{xk}：xk是P(x,k)的最优解.因此有P(xk+1,k+1)≥P(xk,k)110,()kkkPx11111(,)()()kkkkkPxfxPx11()()kkkfxPx1(,)kkPx(,)kkPx得最优解xk=x(k).min(,)()()kkPxfxPx外罚函数法(收敛性质)：P(xk+1,k+1)≥P(xk,k)11()()()()kkkkkkfxPxfxPx11()()[()()]kkkkkfxfxPxPxxk+1是P(x,k+1)最优解1()()kkkfxPx111()()kkkfxPx111[()()]()()kkkkkPxPxfxfx因此111[()()][()()]kkkkkkPxPxPxPx110()[()()]kkkkPxPx1()()kkPxPx1kk再由上面(绿色)标示的不等式,有1()()kkfxfx1()()kkfxfx定理1（外罚函数法收敛性）设优化问题与增广目标函数的整体最优解分别是x*与xk,对于正数序列{k},k+1≥k,且k→+∞,则由SUMT外点法产生的点列{xk}的任何聚点x必是约束优化问题的整体最优解.min()fxs.t.()0,1,2,,igxim()0,1,2,,jhxjl无约束问题min(,)()()kkPxfxPx得最优解xk=x(k).注:所谓聚点,是指子序列的极限.例如，点列1,1/2,-1,1,1/3,-1,1,1/4,-1,···有三个收敛子列，因而有三个聚点1,0,-1.证明目标函数的整体最优解,xk是P(x,k)最优解P(xk,k)存在极限,设为p0.单调有界数列必收敛f(xk)存在极限,设为f0.单调有界数列必收敛不妨设xk→x.由于x*和xk分别是原问题与增广从而0*(),Px***()()()kfxfxPx()()(,)kkkkkfxPxPx11(,)(,)kkkkPxPx1()()kkfxfx()(,)()kkkkkPxPxfx00pfk0()kPx0()kPx0?()kkPx注:对由于xk→x,即x为可行解.而x*为整体最优解,所以f(x*)≤f(x).根据xk→x以及f(x)≤f(x*).因此f(x)=f(x*).()Px且连续,因此*()(,)(),kkkfxPxfx0().Px又得到两边取极限,可得f0=p0.且0().kkPx*()(,)()()()kkkkkkfxPxfxPxfx这是在算法中取作为终止准则的原因.()kkPxf(x)=f(x*)所以x也是整体最优解.例3解取增广目标函数为求解约束优化问题42112min()(2)(2)fxxxx2120xxs.t.P=(x1-2)4+(x1-2x2)2+σ(x12-x2)2x0=(2,1)T,σ1=0.1,c=10,ε=10-3.对于无约束优化问题,采用重新开始的PRP算法(e=10-3)求解.得到的结果见下表.算例(外罚函数法)精确解(0.94558299,0.89412720)T.二．内罚函数法内部惩罚函数法是在约束集D的内部靠近边界的地方，我们给目标函数以一个较大的惩罚项，以让目标函数的最小值点保持在约束集D的内部，并且不断减小惩罚项的值，从而最终求得原问题的最优解。D1、不等式约束问题min()fx()0,1,2,,igxims.t.考虑不等式约束问题.当x从可行域的内部趋于边界时,至少有一个gi(x)趋于零,因此我们构造下面的增广目标函数其中或称为内罚函数或障碍函数(Barrierfunction),参数r称为罚因子.012{|(),,,,}niDxRgxim(,)()()BxrfxrBx11()()miiBxgx1()ln()miiBxgx当x为可行域D的内点时,当x接近D的边界时,令正数列{rk}逐步减小,并趋于零,则原约束问题转化为系列无约束问题.()Bx的值是有限的正数,而r0很小,几乎不受惩罚.的值趋于无穷大,受惩罚很大,迫使极小点落在D的内部,最终逼近f(x)的约束极小点.()Bx内罚函数法(算法步骤)：得最优解xk=x(rk).Step1以xk-1为初始点解无约束问题取控制误差ε0,罚因子缩小系数0c1,初始点x0,初始罚因子r1,令k=1.Step2判别是否满足：若是，则以xk为问题的近似最优解,否则,令rk+1=crk,k=k+1,转Step1.min(,)()()kkBxrfxrBx(),kkrBxStop;(),kkrBx例4解取增广目标函数为求解约束优化问题3121min()(1)3fxxx110,xs.t.20x3121212111131(,,)()()Bxxrxxrxx令得当r→0时,得x*=(1,0)T,f*=8/3.21211101()()Brxxx22210Brxx1()(,),Txrrr一般而言,B(x,r)的最优点要用无约束问题的算法来求解.取x0=(3,4)T,r1=10,c=1/10,=10-3.对于无约束问题,采用重新开始的PRP算法(=10-3)求解.得到的结果见下表.注:在求解无约束问题时,要注意限制一维搜索的初始区间,即保证迭代点始终在可行域之内.在本问题中,如果对一维搜索的初始区间不加限制,函数值会趋于负无穷.算例(内罚函数法)精确解(1,0)T.定理2（内罚法收敛性）引理关于内罚函数法,有类似于外罚函数法的收敛性结论.对于由SUMT内点法产生的点列{xk},总有B(xk+1,rk+1)≤B(xk