最优化方法--第三章(罚函数法)

罚函数法内点法外点法一二简介三混合法四一、罚函数法简介..0,1,,,0,1,,.minnRieiefstgiImhiEmmxxxx借助罚函数将约束非线性规划转化为一系列无约束问题，通过求解无约束问题来求解约束非线性规划，所以也称为序列无约束极小化技术(sequentailunconstrainedminimizationtechnique,简称SUMT)根据约束特点（等式或不等式）构造某种罚函数p(x)，把它加到目标函数中去，将约束非线性规划转化为一系列无约束问题：这种惩罚策略，对于在无约束的求解过程中企图违反约束的迭代点给予很大的目标函数值，迫使无约束问题的极小点或者无限地向可行域D靠近，或者一直保持在可行域D内移动，直到收敛到原来约束最优化问题的极小点。min(,)()()Fxfxpx罚因子()px惩罚函数惩罚项..0,1,,,0,1,,.minnRieiefstgiImhiEmmxxxx()0,()0,pxxDpxxD不改变可行域局部极小值，可以将约束域之外的局部极小值变大。一、罚函数法简介惩罚函数法分类外点法：对违反约束的点在目标函数中加入相应的惩罚，可行点不予惩罚，这种方法的迭代点一般在可行域D的外部移动；内点法:对从内部企图穿越可行域D边界的点在目标函数中加入障碍，距边界越近，障碍越大，在边界上给予无穷大的障碍，从而保证迭代点一直在可行域内部移动；混合法：将外点法和内点法结合，两种惩罚函数联合使用。一、罚函数法简介()0,pxxD()0,pxxD罚函数p(x)应满足的性质(1)p(x)连续(2)(3)min(,)()()FxMfxMpx若是的最优解，且，则也是的最优解。*xMmin(,)FxM*xMD*xMDmin()xDfx证明：因为是的最优解，所以*xMmin(,)FxM*((),)(,),nFxMMFxMxR*,xMD又*0,pxM故所以,xD*(,)FxMM*xMD**fxMMpxMfxMpxxD=fx*=fxM(,)FxM二、外点法一般来说，仅在M充分大时才成立，但在实际计算中，过大的M会造成无约束问题的求解困难，因此取一个递增且趋于的罚因子序列，即然后求解一系列无约束问题*xMDmin(,)FxMkMmin(,)kFxM1210......,kkkMMMMM且()0,pxxD()0,pxxD(1)p(x)连续(2)(3)罚函数p(x)的构造()()max(),0=2iiigxgxgx2211()(max(),0)()mlijijpxgxhx二、外点法外点罚函数法算法步骤1：给定初始点，初始罚因子(可取),精度0x10M11M0,:1.k2：以初始点，求解无约束优化问题1kxmin(,)()()kkFxMfxMpx2211()(max(),0)()mlijijpxgxhx得到极小点，记为，其中*()kxMkx3：若，则停止计算，得到近似极小点；()kkMpxkx1kkMcM用解析法求驻点或者用无约束优化方法求解()0kpxkxD[2,50]c[4,10]c常取否则，令，置k:=k+1，转步骤2。二、外点法1(,)FxM2(,)FxM)x(f(,)kFxMD*xx11,,,kkkkFxMFxM(,)()()kkkkkFxMfxMpxmin(,)()()kkFxMfxMpxkM()0kpx最优解记为kx()0kkMpx因为时，故(,)kkFxM()kpx()kfx若无约束优化问题的最优解始终位于可行集之外二、外点法引理：对于由外点法产生的点列,1,kxk总有：11(1),,,kkkkFxMFxM算法收敛性分析1(2),kkpxpx1(3).kkfxfx11,()0kkkMMpx,kkxFxM是的最优解.11,,kkkkFxMFxM故证明：(1)对于由外点法产生的点列,1,kxk总有：11111,()()kkkkkFxMfxMpx11()()kkkfxMpx1,kkFxM,kkFxM(,)()()kkFxMfxMpx二、外点法,kkxFxM是的最优解.证明：(2)1(,)(,)kkkkFxMFxM()()kkkfxMpx11()()kkkfxMpx11,kkxFxM是的最优解.111(,)(,)kkkkFxMFxM111()()kkkfxMpx11()()kkkfxMpx110()()kkkkMMpxpx1kkMM1()()kkpxpx111()()[()()]kkkkkfxfxMpxpx11()()[()()]kkkkkfxfxMpxpx(3)1(,)(,)kkkkFxMFxM()()kkkfxMpx11()()kkkfxMpx又由(2)1,kkpxpx11()()()()kkkkkkfxMpxfxMpx1()()kkfxfx二、外点法定理：设约束问题和无约束问题的最优解为和*xkx取序列1,,kkkMMM且,kM则由外点法产生的点列kx的任何聚点x~必是约束问题的最优解。证明：不妨设.kxx因为*x和kx分别为约束问题和无约束问题的最优解，且*0,px所以有：***kfxfxMpxkkkfxMpx,kkFxMkfx*(),()kkkfxFxMfx,kkxFxM是的最优解.二、外点法,kkFxM为单调有界序列，设其极限为0.F00lim,kkkkFxMfxFf,kMx~为可行解。*x为最优解；*fxfx*limkkfxfxfx*fxfx即x为约束问题的最优解．*(),()kkkfxFxMfx1()(),kkfxfx又kfx为单调有界序列，设其极限为0.f故而所以lim0kkpxlim,kkpxpx*(),()kkkfxFxMfx11,,kkkkFxMFxMlimkkkMpx故又二、外点法例：用外点罚函数法求解如下优化问题：221212min2..10xxstxx解：问题只有不等式约束，对应的罚函数为:212()min1,0pxxx(,)kFxM22121222212121221211kxxxxxxMxxxx若若用解析法求F(x,Mk)的驻点，令11211212121(,)02211kkxxxFxMxMxxxxx若若二、外点法𝑥12+2𝑥22+𝑀𝑘min𝑥1+𝑥2−1,0221221212241(,)04211kkxxxFxMxMxxxxx若若当时，121xx10x2x，舍去该点；当时，由121xx12(,)(,)0kkFxMFxMxx，得到11221222104210kkxMxxxMxx所以122,2323kkkkMMxxMM，令kM，得到*2/3,1/3Tx二、外点法例：求下述约束优化问题的最优点。min.f(x)=xs.tg(x)=1-x≤0解新目标函数：时。时；11)1(,2xxxxrxrxkk外点罚函数法特点初始罚因子要选择得当，否则会影响迭代计算的正常进行，许多计算表明，取常常可以取得满意的效果；按经验公式计算值1000.02max1,,iMimmgxfx初始点可以任选，对等式约束和不等式约束均可适用；11M1M通常取c=[5,10]。罚因子Mk递增(→∞)，,递增系数c,c11kkMcM二、外点法每个近似解往往不是可行解，这是某些实际问题所无法接受的。内罚函数法可解决外点法中要求,kM而太大将造成增广目标函数,kFxM的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解。乘子法可解决kMkx如果在可行域外目标函数f(x)的性质复杂或者没有定义时，外点法不适用了。二、外点法三、内点法迭代点在可行域的内部移动，内点法要求迭代点在可行域内部移动，初始点必须是内点，可行域的内部必须是非空的，内点法只能处理不等式约束。内点罚函数法内点罚函数法又称为障碍函数法。min()..()0,1,...,ifxstgxim穿越边界，从而将最优解“挡”在可行域内。距边界越近障碍越大，相当于在可行域边界上筑起一道很高的“围墙”，阻止迭代点施加惩罚(加入障碍)，并对接近可行域边界的点19当惩罚因子趋近与零时，惩罚函数的极小点就是原约束问题的最优点。惩罚函数的有效区域是约束的可行域，目标函数在可行域内的所有点都受到惩罚，越靠近边界惩罚越多。不同的惩罚因子对应不同的惩罚函数，惩罚因子越小，惩罚函数的极小点越接近与边界处的最优点。可行域极小值点结构破坏内点罚函数构造(,)()()kkFxrfxrBxB(x)满足下面的条件：B(x)在可行域D的内部连续；intD()Bx1()ln()miiBxgx11()()miiBxgx0,kr121......,0kkkrrrrr且B(x)≥0；当x趋向可行域的边界时min()..()0,1,2,...,ifxstgximmin(,)()()..intkkFxrfxrBxstxD从形式上看，内点法对应的问题仍是一个约束优化问题；但从计算的观点看，是一个无约束优化问题。在可行域的边界附近，问题的目标函数值趋于，只要从可行域D的任何一个内点开始迭代，并注意控制一维搜索的步长，就可使得迭代点不越过可行域，因此不必直接地与约束问题打交道。kxkr若原问题的解位于边界，越小，障碍项所起的作用越小，越接近真解。()krBx内点罚函数法算法步骤1.给定初始点，初始罚因子(可取),精度0intxD10r110r0,:1.k2.以初始点，求解无约束优化问题1kxmin(,)()()kkFxrfxrBx得到极小点，记为，其中*()kxrkx3.若，则停止计算，得到近似极小点；否则，令，置k:=k+1，转步骤2。()kkrBxkx1kkrcr或者0.1c11()()miiBxgx1()ln()miiBxgx引理：对于由内点罚函数法产生的点列,1,kxk总有：收敛性分析11(1),,,kkkkFxrFxr1(2),kkBxBx1(3).kkfxfx收敛性定理：设可行域D的内点集非空，int0,1,2,...,niDxRgximxf在D上存在极小点,*x对严格单减正数列,0kr是约束问题的最优解。kkkrrr1:则由内点法产生的点列kx的任何聚点x~例用内点法求解：解：构造障碍函数312121min()(1)3..100fxxxstxx31212111(,)(1)31kkFxrxxrxx1211()1Bxxx用解析法求函数F的极小点21211222(1)0110kkrFxxxrFxx