[理学]1120 罚函数法 罚函数法与乘子法合订

《[理学]1120 罚函数法 罚函数法与乘子法合订》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2惩罚函数法基本思想：通过引入惩罚函数，将求解约束非线性规划问题转化为求解一系列无约束非线性规划问题．具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解（准确地说，是将这些无约束问题的极小点依次作为迭代点）．根据惩罚函数表达式（构造方法的不同），形辅助函数:外点罚函数法、内点罚函数法、乘子法(外点罚函数法的一种推广和发展)．成不同的罚函数法。我们重点介绍三种：作辅助函数:考虑如下问题：做法：其中不断循环求解.接下来求解并不断改变一、外点惩罚函数法—外点法1.解析法：(1)构造:其中一般取是很大的正数．得最优解

2、(2)求解:(3)令有即得原问题的最优解.2.罚函数的特点分析：当不是可行点时，又因是大正数．故此很难成为的极小点.因此，按上策略得到的的极小点应充分靠近可行域，逐渐接近原问题的最优解．其中一般取是很大的正数．辅助函数:当是可行点时，例1：求解等式约束问题:分析:图解法求出最优解下面看用外点法如何求解.即如何构造惩罚函数？解：构造罚函数和辅助函数：其中是很大的正数．令：得：并且可见正定.又因该点处令时，有：即：无约束问题的最优解的极限为原问题的最优解．处取得极小值.因此在点例2：用外点罚函数法求解：解：即：因此：作辅助函数令：得：又因该点处并且可见正定.同理：处取得极小

3、值.因此在点令得：所以原问题的最优解及最优值分别为：易验证即满足约束条件,3算法实现对于上述解法中,的选取对问题的求解十分重要,一般策略是取一个趋于无穷大的严格递增正数列得极小点序列然后求解随着迭代次数(k)的增加，该点列渐渐收敛于原问题的极小点.下面看一下外点法的求解问题的数值算法.算法实现（数值解法）1)给定初始点初始惩罚因子允许误差放大因子否则，令返回2)．3)若停止运算，取作为近似解．令2)以为初始点，求解得极小点，记作根据经验,常常取收敛性定理定理设的极小点为则会出现以下两种情况：（1）如果存在某个满足则结束运算;无穷点列（2）如果上述情况不发生,若则这时就得

4、到一个4注意事项：(1)用上述方法得到得往往不满足约束条件,即从可行域外部趋向于的．因此叫外罚函数法．因此，上述算法（数值解法）又称SUMT外点法．(2)该方法是通过求解一系列无约束最优化问题来求解约束最优化问题的方法，这又被称为序列无约束极小化技术SUMT.(SequentialUnconstrainedMinimizationTechnique)5算法评价（优缺点）(1)若有了求解无约束问题的好算法，则利用外罚函数法求解约束问题很方便．(2)每个近似解可能不是可行解，这是某些实际问题所无法接受的．内点罚函数法可以解决．而(3)理论上已证明取越大越好，越大将造成增广目

5、标函数的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解．乘子法可解决这个问题．二、内点罚函数法(碰壁函数法)—内点法基本思想:极小点得新的可行点,注意：该方法只适合于不等式约束问题，并且要求可行域的内点集非空，不能包含孤立点或孤立线段.直观看来,而且中的点可以任意接近于的任一点.从一个可行点出发,通过求辅助函数即在可行点之间进行迭代,使迭代点逐渐靠近或收敛于最优点.最终惩罚策略：在可行域的边界上筑起一道很高的“围墙”,当迭代点靠近可行域的边界时，目标函数值陡然增大,这相当于对它进行惩罚，从而阻止迭代点穿越边界，这样就可以把最优解“挡”在可行

6、域内了．其中：定义惩罚项(碰壁项)函数满足:作辅助函数不断循环求解.接下来求解并不断改变1.解法：(1)构造:得最优解(2)求解:(3)令有即得原问题的（近似）最优解.或其中：2罚函数的特点构造：其中：或分析：为可行域的内点时，为有限正数，几乎不受惩罚；接近边界时，趋于无穷大，施以很重的惩罚；这样迫使极小点落在可行域内，逐渐逼近极小点．例3：用内点罚函数法求解：令：解：作辅助函数所以令有：再注意到可验证该点处的海森矩阵正定,所以是的极小点.3.算法实现Step2:以为初始点求无约束问题：得最优解,记作Step3:若则停；否则转Step4Step4:令转Step2.Ste

7、p1:给出(要求是可行点)，罚因子缩小系数令例4：用SUMT内点法求解：取迭代结果见下表：注:在求解无约束问题时,要注意限制一维搜索的初始区间,即保证迭代点始终在可行域之内.在本问题中,如果对一维搜索的初始区间不加限制,函数值会趋于负无穷.１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