第八章内点法和外点法.pdf

《第八章内点法和外点法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、建模方法与应用主讲人：徐猛北京交通大学交通运输学院建模方法与应用9.约束优化问题(II)本节课内容：惩罚函数的概念和性质惩罚函数法(SUMT外点法)障碍函数法(SUMT内点法)建模方法与应用9.基本思想惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题转换为一系列无约束非线性规划问题。所以也称序列无约束极小化技术(SequentialUnconstrainedMinimizationTechnique,SUMT)惩罚函数法的分类：惩罚函数法（SUMT外点法），障碍函数法（SUMT内点法）。建模方

2、法与应用9.惩罚函数的性质和构造考虑MP问题：minf(x)(4.1)s.t.gi(x)0,i1,,p(4.2)hj(x)0,j1,,q(4.3)*ngi(x)0,i1,,p设xXxR(4.4)h(x)0,j1,,qi**则g(x)0,i1,,p，h(x)0,j1,,qij建模方法与应用9.惩罚函数的性质和构造对上面的约束优化问题,定义惩罚函数Fx,MfxMpx(4.5)n其中M0为常数，称为惩罚因子，px是定义在R上的一个函数，称为惩罚项，它满足：（1）px是连续的n（2）对任意的xR，有p

3、x0（3）当且仅当px0时，xX建模方法与应用9.约束优化问题(II)对上面的不等式约束，定义0g(x)0igi(x)2,i1,2,,p（4.6）gi(x)gi(x)0对上面的等式约束，定义2gpj(x)hj(x),j1,2,,q（4.7）令Lpq，于是，惩罚函数为LFx,MfxMgx（4.8）kkii1其中，Mk0，且M1M2MkMk1。建模方法与应用9.约束优化问题(II)Lpxgx具有上述的容易验证，上面定义的惩罚项ii1三条性质。L（1）显然gix，i1,,

4、L是连续的，因此pxgix连续。i1Lngx。所以（2）对所有的xR，显然有i0pxgix0。i1L（3）当xX时，gix0，故pxgix0；反之，若i1Lpxgix0，由于gix0，所以gix0，i1,,L。i1建模方法与应用9.约束优化问题(II)由上述分析，当xX时，则gix0，i1,,L；当约束条件被破坏，即当xX时，则至少存在一个i，1iL，L使得gix0，从而pxgix0。约束条件被破坏得约厉i1L害，则px

5、gix0取值越大，从而Fx,MfxMpx也i1就越大。即对约束条件被破坏是一种惩罚，M越大，则惩罚L得越厉害。反之，当约束条件满足时，则pxgix0，i1这时无论M多大，Fx,Mfx，即约束条件满足时，不受惩罚，由此可见惩罚项以及惩罚函数的意义。建模方法与应用9.约束优化问题(II)关于惩罚因子Mk的取法，根据计算经验可以选取MMck1k，c2,50，常取c4,10。计算方法用惩罚函数法求解约束优化问题(4.1)-(4.3)的计算步骤总结如下：01．选取M10，精度0,c2，初始点x，令k1；k12

6、．以x为初始点，求解无约束优化问题LminFx,MfxMgxkki（4.9）i1k设其最优解为xxMk。(k)*(k)3．若Mkpx，则取xx，迭代结束；否则，令Mk1Mkc，kk1，转回第2步。建模方法与应用Lpxgx可以采用（4.6）说明：在式（4.9）中，惩罚项ii1和（4.7）式的定义方法，也可以采用其它定义方法，只要能保证px具有前面所述三条性质即可。建模方法与应用9.约束优化问题(II)[例]利用SUMT外点法求解非线性规划22minf(x)(x13)(x22)h1(x)x1x240建模方

7、法与应用9.约束优化问题(II)222解：令F(x,M)(x13)(x22)M(x1x24)F2x32M(xx4)x1121F2x22M(xx4)x2212FF令x10,x20，得5M33M2x1，x22M12M1222FFF因22M1，22M1，2Mx1x2x1x22(M1)2M2故F。2M2(M1)建模方法与应用