运筹学13 惩罚函数法

《运筹学13 惩罚函数法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@gmail.com,Tel:62281308,Rm:主楼814§13，罚函数法TPSHUAI113惩罚函数法考虑约束问题min()fxst..()gxi0,i1,...,m（13.1.1）()hx0,j1,2,...lj其中(),()fxgx和hx()连续.ij向量形式min()fx其中st..()gx0,()gx((),...,gxg())xT1m()hx0T()=((),...())hxhxgx1lTPSHUAI213惩罚函数法令问题的可行域为：gx()0,i1,...,.miDx.

2、hx()0,j1,...,lj如何求解约束问题？可行方向法：沿下降可行方向搜索其他方法？序列无约束优化算法：通过求解一系列无约束问题的解来近似约束问题的解。罚函数法是序列无约束问题算法的典型代表。TPSHUAI313.1外点惩罚函数法罚函数法的基本思想是构造辅助函数F,把原来的约束问题转化为求极小化辅助函数的无约束问题例如可以定义函数F:RnR为fxx(),DFx(),xD易见约束问题(13.1.1)的解等价于nmin(),FxxR的解但由于F在可行域D的边界不连续.因此难以直接由求解F的极小值来求问题(13.1.1)的极小点.TPSHUAI413.1外点罚函数

3、法于是构造辅助函数极为重要！！！外点法的基本思想是构造辅助函数nF:RR(0)函数FD在可行域的内部的取值与问题(13.1.1)的目标函数ff的取值相等,而在可行域的外部取值远远大于目标函数的值.换言之,,对可行域外部点的目标函数值加以惩罚使得无约束问题minFx()的解是约束问题(13.1.1)的近似解.且当时,问题minFx()的解x()趋于约束问题的解.TPSHUAI513.1外点罚函数法对于约束问题min()fx（13.1.2）st..()hx0,j1,2,...lj可定义辅助函数:l2Fx1(,)fx()hxj()(13.1.3)j1参数是

4、很大的正数.于是(13.1.2)转化为:minFx(,)(13.1.4)1TPSHUAI613.1外点罚函数法对于不等式约束问题min()fx(13.1.5)st..()gx0,i1,2,...mi可定义辅助函数:m2Fx2(,)fx()(max{0,gxi()})(13.1.6)i1参数是很大的正数.于是(13.1.2)转化为:minFx(,)(13.1.7)2TPSHUAI713.1外点罚函数法对于一般形式的问题(13.1.1).可定义辅助函数Fx(,)fx()Px()(13.1.8)其中P(x)具有如下形式:mlPx()(())+gxij((

5、))(13.1.9)hxij11连续函数和满足0,yy00,0()yy,().0,yy00,0TPSHUAI813.1外点罚函数法连续函数和的典型取法有(max{0,gx()})i=hx()(1,1)j于是把约束问题(13.1.1)转化为无约束问题min(,)Fxfx()Px()(13.1.10)其中是很大的正数,P(x)是连续函数TPSHUAI913.1外点罚函数法2例1min()fxx..()stgxx10(13.1.11)该问题的可行域D=-,-1],最优解x*=-1m12令Fx(,)fx(

6、)(max{0,gxi()})2i1221xx+(max{0,1})(13.1.12)2min(,)Fx的解为x()2xx()1*,2TPSHUAI1013.1外点罚函数法罚因子的选取非常重要!!!一般的策略是:取一趋向无穷大的严格递增正数列{},k从某个开始,,对每个k求解1min(fxxP)()(13.1.13)k从而得到一个极小点的序列{}x在适当条件下,此序列k收敛于约束问题的最优解.序列无约束极小化方法(SUMT)TPSHUAI1113.1外点罚函数法外点法(0)1,给定初点xc,初始罚因子,放大系数1

7、,允许误差10,置k1.(k1)2,以x为初点,解无约束问题min()fxPx()k()k得极小点为x()kk()3,若Px(),停止,得点x;否则,令c.kkk+1置kk:1,转2TPSHUAI1213.1外点罚函数法1.3收敛性()kk(1)引理13.1.1设0,x和x分别为取罚因kk1子和时无约束问题的极小点,则下列各式成立kk1()kk(1)1,(Fx,)Fx