1120-罚函数法-(罚函数法与乘子法合订)

Page1§2惩罚函数法基本思想：通过引入惩罚函数，将求解约束非线性规划问题转化为求解一系列无约束非线性规划问题．具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解（准确地说，是将这些无约束问题的极小点依次作为迭代点）．Page2根据惩罚函数表达式（构造方法的不同），形辅助函数:,FxfxPx外点罚函数法、内点罚函数法、乘子法(外点罚函数法的一种推广和发展)．成不同的罚函数法。我们重点介绍三种：Page3作辅助函数:,FxfxPxmin(),..()0,1,,()0,1,,nijfxxRstgximhxjp考虑如下问题：做法：其中不断循环求解.0是常数，称为惩罚因子;nRPx是定义在上的一个函惩罚项数，称为，它满足：(1)Px是连续的；(2),nxRPx对任意的有0；(3).xPx当且仅当是可行点时，=0接下来求解(,),MinFx并不断改变,一、外点惩罚函数法—外点法Page4min(),..()0,1,,()0,1,,nijfxxRstgximhxjp1.解析法：(1)构造:,FxfxPx11max0,pmijijPxgxhx其中一般取2.1,1,0是很大的正数．x得最优解(2)求解:,nxRMinFxfxPx,(3)令,xx有即得原问题的最优解.Page52.罚函数的特点分析：当x不是可行点时，0,Px又因是大正数．故此x很难成为Fx，的极小点.因此，按上策略得到的,Fx的极小点应充分靠近可行域，逐渐接近原问题的最优解．min(),..()0,1,,()0,1,,nijfxxRstgximhxjp11max0,pmijijPxgxhx其中一般取2.1,1,0是很大的正数．辅助函数:,FxfxPx当x是可行点时，()0,(,)().PxFxfxPage6例1：求解等式约束问题:222121,minxxxxf02.21xxts分析:图解法求出最优解.1,1*Tx下面看用外点法如何求解.即如何构造惩罚函数？Page7解：构造罚函数和辅助函数：1222212,2Fxxxxx其中是很大的正数．12221xx令：120FFxx得：22222121221,21,2FFFxxxx2212221F并且0,可见正定.又因该点处Page8令时，有：**1212,,1,1TTTxxxx即：无约束问题的最优解的极限为原问题的最优解．处取得极小值.22,2121Tx因此,Fx在点Page9例2：用外点罚函数法求解：221212min32.40fxxxstgxxx解：,Fx即：22121222212121232,40,324,40xxxxFxxxxxxx因此：11211212123,42324,4xxxFxxxxxx作辅助函数212max0,4xx221232xxPage10令：120FFxx得：125332,2121xx又因该点处22222121221,21,2FFFxxxx2212221F并且0,可见正定.同理：21221212222,42224,4xxxFxxxxxxPage11处取得极小值.5332,2121Tx因此,Fx在点令得：53lim,.22Txx**531,,.222Txfx所以原问题的最优解及最优值分别为：易验证00,gx即满足约束条件,Page123算法实现对于上述解法中,的选取对问题的求解十分重要,,k一般策略是取一个趋于无穷大的严格递增正数列得极小点序列(,)()kkMinFxfxPx.kx然后求解随着迭代次数(k)的增加，该点列渐渐收敛于原问题的极小点.下面看一下外点法的求解问题的数值算法.Page13算法实现（数值解法）1)给定初始点0,x初始惩罚因子允许误差10,放大因子否则，令1,1,kkCkk返回2)．0,1,C3)若(),kkPx停止运算，取作为近似解．kxx令1.k2)以1kx为初始点，求解得极小点，记作(,)()nkkxRMinFxfxPx.kx根据经验,常常取11,4,10.CPage14收敛性定理定理设(),kkxx的极小点为(,)nkxRMinFx则会出现以下两种情况：（1）如果存在某个01k0kxS（可行域）满足则0,kxx结束运算;1,kkx无穷点列（2）如果上述情况不发生,若(),(),()ijfxgxhxC，lim.kkxx则这时就得到一个Page154注意事项：(1)用上述方法得到得kx往往不满足约束条件,即从可行域外部趋向于*x的．因此叫外罚函数法．因此，上述算法（数值解法）又称SUMT外点法．(2)该方法是通过求解一系列无约束最优化问题来求解约束最优化问题的方法，这又被称为序列无约束极小化技术SUMT.(SequentialUnconstrainedMinimizationTechnique)Page165算法评价（优缺点）(1)若有了求解无约束问题的好算法，则利用外罚函数法求解约束问题很方便．(2)每个近似解kx可能不是可行解，这是某些实际问题所无法接受的．内点罚函数法可以解决．而(3)理论上已证明k取越大越好，k越大将造成增广目标函数,Fx的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解．乘子法可解决这个问题．Page17二、内点罚函数法(碰壁函数法)—内点法基本思想:极小点得新的可行点,注意：该方法只适合于不等式约束问题，并且要求可行域的内点集intS非空，S不能包含孤立点或孤立线段.直观看来,而且intS中的点可以任意接近于S的任一点.从一个可行点0xS出发,通过求辅助函数即在可行点之间进行迭代,使迭代点逐渐靠近或收敛于最优点.最终Page18惩罚策略：在可行域的边界上筑起一道很高的“围墙”,当迭代点靠近可行域的边界时，目标函数值陡然增大,这相当于对它进行惩罚，从而阻止迭代点穿越边界，这样就可以把最优解“挡”在可行域内了．其中：定义惩罚项(碰壁项)函数(),Bx满足:(1)Bx是连续的；(2),xBx对任意的有0；(3).xSBx当趋于的边界时，作辅助函数,,0FxrfxrBxr称为碰壁因子不断循环求解.接下来求解(,),MinFxr并不断改变,rPage191.解法：min(),..()0,1,,nifxxRstgxim(1)构造:,,0FxrfxrBxr为很小的正数rx得最优解(2)求解:int,xSMinFxrfxrBx0,r(3)令,rxx有即得原问题的（近似）最优解.11miiBxgx或1lnmiiBxgx其中：Page202罚函数的特点min(2)nfxxR..01,2,istgxim构造：,,0FxrfxrBxr其中：11miiBxgx或1lnmiiBxgx分析：x为可行域的内点时，Bx为有限正数，几乎不受惩罚；x接近边界时，Bx趋于无穷大，施以很重的惩罚；这样迫使极小点落在可行域内，逐渐逼近极小点．Page21例3：用内点罚函数法求解：312121min13.100fxxxstxx令：21211101Frxxx22210Frxx31212111,131Fxrxxrxx解：作辅助函数0r其中为很小的正数Page22所以1rxrr令0r有：**8()1,0,3Txrxf再注意到,xS可验证该点处的海森矩阵3222101120rrrFr正定,所以xr是,Fxr的极小点.Page233.算法实现Step2:以1kx为初始点求无约束问题：int,kxSMinFxrfxrBx得最优解,记作.kxStep3:若,kkrBx则*,kxx停；否则转Step4Step4:令1,kkrcr,1kk转Step2.Step1:给出0,nxR(要求是可行点)，4100罚因子,1011rr缩小系数0.1,cc.1k令Page24例4：用SUMT内点法求解：001.131min21231xxtsxxxf取013,4,10,0.1,0.1Txrc迭代结果见下表：注:在求解无约束问题时,要注意限制一维搜索的初始区间,即保证迭代点始终在可行域之内.在本问题中,如果对一维搜索的初始区间不加限制,函数值会趋于负无穷.Page25１10(2.0402,3.1623)12.529012.7755２1(1.1473,0.3162)3.61650.9951３0.1(1.0488,0.1000)2.96670.3049４0.01(1.0157,0.0316)2.76160.0953５0.001(1.0016,0.0316)2.70460.0941kkr1()kTx1kf1kkrBxPage26收敛性定理定理任给初始可行点，记由上述若(),()ifxgxC，lim.kkxx则(),kkxxrSUMT内点罚函数法产生的点列为Page274.注意事项1）初始点x0的选取使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.2）惩罚因子初值r0的选取惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当r0Page283)惩罚因子的缩减系数c的选取在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为:1(1,2,...)kkrcrk式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.1~0.7之间。4).由于无约束优化问题的解法目前已经有许多很有效的算法，如DFP算法，BFGS法等，所以在求解一些复杂的约束优化问题时，工程技术人员一般乐于采用内点罚函数法。此方法简单、易懂。Page295).尽管外点法和内点法目前都已被广泛应用，但算法中惩罚因子的选取对收敛速度的影响比较大。惩罚因子的增大（外点法）与缩小（内点）使得问题的求解变得很困难，有时甚至会使增广目标函数趋于病态。一些学者对