最优化 18 惩罚函数法.docx

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

1、第13章惩罚函数法SUMT(Sequentialunconstrainedminimizationtechnique)序列无约束最小化技术ì外点法：迭代点在可行域外部移动罚函数法íî内点法：迭代点在可行域内部移动外点法ìminï(A)ís.t.ïîf(x)gi(x)³0i=1,2,,mhj(x)=0j=1,2,,l其中f(x),gi(x)(i=1,2,,m),hj(x)(j=1,2,,l)在En上连续。S={x

2、gi(x)³0(i=1,2,,m),hj(x)=0(j=1,2,,l)}引入罚项mlp(x)=å[

3、gi(x)]+å[hj(x)]i=1j=1其中(y),(y)是连续函数，且满足ì(y)=0当y³0í当y<0î(y)>0ì(y)=0当y=0í当y¹0î(y)>0函数和的典型取法：[gi(x)]=[max{0,-gi(x)}][hj(x)]=hj(x)其中³1,³1均为给定常数，通常取==2。ìminïís.t.ïîf(x)gi(x)³0i=1,2,,mhj(x)=0j=1,2,,lminF(x,)=f(x)+p(x)émlùminF(x,)=f(x)+êå[gi(x)]+å[hj(x)]úëi=1j=1û其

4、中是很大的正数。minf(x)=(x1-1)2+x22s.t.g(x)=x2-1³0解：定义罚函数F(x,)=(x-1)2+x2+[max{0,-(x2-1)}]212ì-1)22x2³1ï(x1+x2=í222ï-1)+(x2-1)x2<1î(x1+x2¶F¶Fì2x2x2³1=2(x1-1)=í+2(x2-1)x2<1¶x2¶x1î2x2令¶F=0¶F=0得¶x2¶x1æxöæ1öæ1öx=ç1÷=ç÷®ç÷(®+¥)xç÷1èøç÷èø2è1+øminx1+x2s.t.x1-x22=0定义罚函数F(x,)

5、=x+x+(x-x2)21212æ1+2(x1-x22)öÑF(x,)=ç÷ç1+2(x-x2)(-2x)÷è122ø令ÑF(x,)=0,得æ111öTæ11öTx=ç-,-÷®ç,-÷(®¥)42è42øèøminf(x)=x1+x2s.t.g1(x)=-x12+x2³0g2(x)=x1³0解：定义罚函数F(x,)=x1+x2+[max{0,x12-x2}]2+[max{0,-x1}]2¶F=1+2[2max{0,x12-x2}x1+max{0,-x1}(-1)]¶x1¶F=1+2max{0,x2-x}(-1

6、)12令¶F=0¶F=0得¶x2¶x1ì2-x2)+2x1=0ï1+4x1(x1íï2-x2)=0î1-2(x1Þx=-1x2=1-112+2(2+2)22æöæ0ö当®+¥时，有çx1÷®ç÷ç÷ç÷èx2øè0ø步骤:1.给定初始点x(0)，初始罚因子1>0(1=1)，放大系数c>1，允许误差>0，置k=1。2.以x(k-1)为初始点，求解无约束问题minf(x)+kp(x)设其极小点为x(k)。3.若kp(x(k))<，则停止计算，得到点x(k)；否则，令k+1=ck，置k:=k+1，返回2。例:用外点法

7、求解min(x-1)2s.t.x-2³0解：取x(0)=0,1=1，令p(x)=[max{0,-x+2}]2则ì0x³2p(x)=í2x<2(-x+2)î第一次迭代求解无约束最优化问题：minF(x,1)=(x-1)2+1´p(x)ì2其中F(x,ï(x-1))=í+1´(-x+2)21ï(x-1)2î解得：x(1)=321x³2x<2令2=10´1=101x(1)2第二次迭代求解无约束最优化问题：minF(x,2)=(x-1)2+10´p(x)ì(x-1)2ï其中F(x,2)=í22ïî(x-1)+10´

8、(-x+2)解得：x(2)=21111令3=10´2=1001x(2)2x³2x<2第三次迭代求解无约束最优化问题：minF(x,3)=(x-1)2+100´p(x)ì2x³2其中F(x,ï(x-1)3)=í+100´(-x+2)2x<2ï(x-1)2î解得：x(3)=201101以此类推，得序列：x*=23，21，201，2001，2111011001引理1对于由外点法所产生的序列{x(k)}，总有(1)F(x(k+1),k+1)³F(x(k),k)(2)p(x(k+1))£p(x(3)f(x(k+1))

9、³f(x(k)(k)))证明：(1)由F(x,)=f(x)+p(x)和k+1>k知F(x(k+1),k+1)=f(x(k+1))+k+1p(x(k+1))³f(x(k+1))+kp(x(k+1))=F(x(k+1),k)x(k)是F(x,k)的极小点,对"x,有F(x,k)³F(x(k),k)ÞF(x(k+1),k)³F(x(k),k)ÞF(x(k+1),k+1)³F(x(k),