第八章-内点法和外点法

建模方法与应用建模方法与应用主讲人：徐猛北京交通大学交通运输学院建模方法与应用9.约束优化问题(II)建模方法与应用本节课内容：惩罚函数的概念和性质惩罚函数法(SUMT外点法)障碍函数法(SUMT内点法)建模方法与应用9.基本思想惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题转换为一系列无约束非线性规划问题。所以也称序列无约束极小化技术(SequentialUnconstrainedMinimizationTechnique,SUMT)惩罚函数法的分类：惩罚函数法（SUMT外点法），障碍函数法（SUMT内点法）。建模方法与应用9.惩罚函数的性质和构造qjxhpixgRxXxiin,,1,0)(,,1,0)(*设考虑MP问题：qjxhpixgtsxfji,,1,0)(,,1,0)(..)(minqjxhpixgji,,1,0)(,,1,0)(**，则(4.1)(4.2)(4.3)(4.4)建模方法与应用9.惩罚函数的性质和构造对上面的约束优化问题,定义惩罚函数xxxMpfMF,其中为常数，称为惩罚因子，是定义在上的一个函数，称为惩罚项，它满足：0MxpnR（1）是连续的xp（2）对任意的，有nRx0xp（3）当且仅当时，0xpXx(4.5)建模方法与应用9.约束优化问题(II)对上面的不等式约束，定义piggggiiii,,2,1,0)(0)()(0)(2xxxx（4.6）对上面的等式约束，定义qjhgjjp,,2,1,)()(2xx（4.7）令qpL，于是，惩罚函数为LiikkgMfMF1,xxx（4.8）其中，0kM，且121kkMMMM。建模方法与应用9.约束优化问题(II)容易验证，上面定义的惩罚项Liigp1xx具有上述的三条性质。（1）显然xig，Li,,1是连续的，因此Liigp1xx连续。（2）对所有的nRx，显然有0xig。所以01Liigpxx。（3）当Xx时，0xig，故01Liigpxx；反之，若01Liigpxx，由于0xig，所以0xig，Li,,1。建模方法与应用9.约束优化问题(II)由上述分析，当Xx时，则0xig，Li,,1；当约束条件被破坏，即当Xx时，则至少存在一个i，Li1，使得0xig，从而01Liigpxx。约束条件被破坏得约厉害，则01Liigpxx取值越大，从而xxxMpfMF,也就越大。即对约束条件被破坏是一种惩罚，M越大，则惩罚得越厉害。反之，当约束条件满足时，则01Liigpxx，这时无论M多大，xxfMF,，即约束条件满足时，不受惩罚，由此可见惩罚项以及惩罚函数的意义。建模方法与应用9.约束优化问题(II)关于惩罚因子kM的取法，根据计算经验可以选取cMMkk1，50,2c，常取10,4c。计算方法用惩罚函数法求解约束优化问题(4.1)-(4.3)的计算步骤总结如下：1．选取01M，精度2,0c，初始点0x，令1k；2．以1kx为初始点，求解无约束优化问题LiikkgMfMF1,minxxx（4.9）设其最优解为kkMxx。3．若)(kkpMx，则取)(*kxx，迭代结束；否则，令cMMkk1，1kk，转回第2步。建模方法与应用说明：在式（4.9）中，惩罚项Liigp1xx可以采用（4.6）和（4.7）式的定义方法，也可以采用其它定义方法，只要能保证xp具有前面所述三条性质即可。建模方法与应用9.约束优化问题(II)[例]利用SUMT外点法求解非线性规划2221)2()3()(minxxfx04)(211xxhx建模方法与应用9.约束优化问题(II)解：令2212221)4()2()3(),(xxMxxMFx)4(2322111xxMxxF)4(2222122xxMxxF令0,021xFxF，得12351MMx，12232MMx因12212MxF，12222MxF，MxxF2212故)1(222)1(22MMMMF。建模方法与应用由于M大于0，故F2是正定矩阵，因此),(MFx在1223,1235MMMMMx处取得极小值。令M，得23,25lim*MMxx，易见0*1xh，所以*x即为xf在约束01xh的极小点。而极小值为21*xf。建模方法与应用9.约束优化问题(II)[例]利用SUMT外点法求解非线性规划2221)2()3()(minxxfx04)(21xxgx解：令000)(2xxxggxgg；xxMgxxMF2221)2()3(),(0032)4(23212111xxggxxxMxxF0022)4(22222122xxggxxxMxxF令0,021xFxF，得12351MMx，12232MMx令M，得23,25lim*MMxx，易见0*1xh，所以*x即为xf在约束01xh的极小点。而极小值为21*xf。建模方法与应用9.约束优化问题(II)[例]利用SUMT外点法求解非线性规划21)(minxxfx0)(2211xxgx0)(12xgx解：构造惩罚函数21222121)(),(xxxMxxMFx])2)([(21112211xxxxMxF)(212212xxMxF对于不满足约束条件的点Txx),(21x，可以有0221xx或01x。令0,021xFxF，得),(minMPx的解为：TMMMM),()(21)1(41)1(212x建模方法与应用9.约束优化问题(II)取4,3,2,1M可得如下结果：1M：T),(16741x，2M：T),(9261x3M：T),(1922981x，4M：T),(20023101x从此结果可知)(Mx从R的外部逐步逼近R的边界，当M趋于无穷时，)(Mx趋于原问题的极小解T)0,0(minx建模方法与应用9.算法收敛性分析设kkMxx)(为无约束优化问题(4.9)的最优解。可以分为两种情况：1．如果某一个0kM(10k)对应的无约束问题(4.9)的最优解Xk)(0x，则)(0kx为原来约束优化问题(4.1)-(4.3)的最优解。证明：因为对一切的Xx，有0xig，Li,,2,1，故00000001)(1,,kLiikkkkkLiikfgMfMFMFgMffxxxxxxxx建模方法与应用9.约束优化问题(II)2．如果第1种情况不发生，即得到一个无穷点列)(kx，Xk)(x，,2,1k这时，可以证明在某些条件下)(kx的任何极限点*x都是原来约束优化问题(4.1)-(4.3)的最优解。首先证明如下两个引理。引理1对1kkMM，下列不等式成立（1）1)1()(,,kkkkMFMFxx(4.10)（2）)1()(kkppxx(4.11)（3）)1()(kkffxx(4.12)建模方法与应用9.约束优化问题(II)证明：（1）kkkkkkkkkkkkkMFpMfpMfpMfMF,,)()()()1()1()1(1)1(1)1(xxxxxxxx即(4.10)式成立。（2）因为)1()1()()(kkkkkkpMfpMfxxxx)(1)()1(1)1(kkkkkkpMfpMfxxxx将上面两式相加，并消去相同的项，得)(1)1(1kkkkkkpMMpMMxx由于1kkMM，故(4.11)式成立。建模方法与应用9.约束优化问题(II)（3）因为)1()1()()(kkkkkkpMfpMfxxxx)1()(kkkkpMpMxx综合上面二式的结果，得(4.12)式。引理2设*x是约束优化问题(4.1)-(4.3)的一个最优解，则对每一个k，有kkkfMFfxxx,)(*。(4.13)证明：因为*x是(4.1)-(4.3)的一个最优解，故X*x，0*xp。从而，0,)()()(***kkkkkkkfMFpMfpMffxxxxxxx建模方法与应用9.约束优化问题(II)定理4.1假设)(xf、)(xig(pi,,2,1)和)(xjh(qj,,2,1)均具在x上连续，)(kx是由惩罚函数法产生的一个序列，则这个序列的任一极限点都是约束优化问题(4.1)-(4.3)的一个最优解。证明：设)(ikx是)(kx的一个收敛的子序列，其极限为x，即xx)(limiki由)(xf为连续函数可知，xxffiki)(lim(4.14)要证明x是约束优化问题(4.1)-(4.3)的一个最优解，即要证明Xx，且)()(min)(*xxxxfffX。建模方法与应用9.约束优化问题(II)1．由上面的引理1和引理2知，kkMF,)(x是一个非减且有上界)(*xf的序列，故***)(,,limxxxfMFMFiikki(4.15)用(4.15)减去(4.14),得xxxfMFpMiikki**)(,lim因为当i时，ikM，且0)(ikpx，所以0lim)(ikipx又因为)(xig(pi,,2,1)和)(xjh(qj,,2,1)均连续，故xp也为连续函数，所以0xp，故Xx。建模方法与应用9.约束优化问题(II)2．由引理2知*)(xxffik，令i，得*xxff而xxxffXmin*，故*xxff，于是必有*xxff。由上面的1和2知，x是约束优化问题(4.1)-(4.3)的最优解。建模方法与应用9.基本思想:障碍函数法惩罚函数法的最大特点是其初始点可以任意选择（不要求是可行点），这虽然给计算带来了很大的方便；但是如果目标函数)(xf在可行域外比较复杂，甚至根本没有定义，外点法就无法使用了。障碍函数法与惩罚函数法不同，它要求迭代过程始终建立在可行的基础之上；即在可行域的内部选取一个初始点，并在可行域的边界上设置一道“屏障”，当迭代过程靠近可行域的边界时，新的目标函数值迅速增大，从而使迭代点始终保持在可行域的内部。建模方法与应用9.惩罚函数的性质和构造仿照惩罚函数法，通过函数叠加的办法来改造原有目标函数，使改造后的目标函数（称为障碍函数）具有这样的性质：在可行域X的内部与边界面较远的点上，障碍函数与原目标函数应尽可能地接近；而在接近边界面的点上，障碍函数取相当大的数值。可以想象，满足这种要求