《罚函数法（罚函数法与乘子法合订）ppt课件.ppt》由会员分享，可在线阅读，更多相关《罚函数法（罚函数法与乘子法合订）ppt课件.ppt（52页珍藏版）》请在三一办公上搜索。
1、2 惩罚函数法,根据惩罚函数表达式（构造方法的不同），形,辅助函数:,外点罚函数法、内点罚函数法、乘子法(外点罚函数法的一种推广和发展),成不同的罚函数法。,我们重点介绍三种：,作辅助函数:,考虑如下问题：,做法：,其中,不断循环求解.,接下来求解,并不断改变,一、外点惩罚函数法外点法,1. 解析法：,2.罚函数的特点,分析：,辅助函数:,解：构造罚函数和辅助函数：,令：,得：,并且,可见,正定.,又因该点处,即：无约束问题的最优解的极限为原问题的最优解,例2：,用外点罚函数法求解：,解：,即：,因此：,作辅助函数,令：,得：,又因该点处,并且,可见,正定.,同理：,所以原问题的最优解及最优值
2、分别为：,3 算法实现,一般策略是取一个趋于无穷大的严格递增正数列,随着迭代次数(k)的增加，该点列渐渐收敛于原问题,的极小点.,下面看一下外点法的求解问题的数值算法.,算法实现（数值解法）,1) 给定初始点,初始惩罚因子,允许误差,放大因子,令,2) 以,为初始点，求解,得极小点，记作,根据经验, 常常取,收敛性定理,定理,则,结束运算;,无穷点列,（2）如果上述情况不发生,若,则,这时就得到一个,4 注意事项：,因此，上述算法（数值解法）又称SUMT外点法,5 算法评价（优缺点）,二、内点罚函数法(碰壁函数法)内点法,基本思想:,极小点得新的可行点,注意：,该方法只适合于不等式约束问题，,
3、通过求辅助函数,即在可行点之间进行迭代,惩罚策略：,在可行域的边界上筑起一道很高的“围墙”,当迭代点靠近可行域的边界时，目标函数值陡然增大,这相当于对它进行惩罚，从而阻止迭代点穿越边界，,这样就可以把最优解“挡”在可行域内了,其中：,定义惩罚项(碰壁项)函数,满足:,作辅助函数,不断循环求解.,接下来求解,并不断改变,1. 解法：,(1)构造:,或,其中：,2 罚函数的特点,构造：,其中：,或,例3：,用内点罚函数法求解：,令：,解：作辅助函数,所以,再注意到,可验证该点处的海森矩阵,正定,3. 算法实现,例4：,用SUMT内点法求解：,取,迭代结果见下表：,注: 在求解无约束问题时,要注意限
4、制一维搜索的初始区间, 即保证迭代点始终在可行域之内.在本问题中, 如果对一维搜索的初始区间不加限制, 函数值会趋于负无穷.,收敛性定理,定理,任给初始可行点，,记由上述,若,则,SUMT内点罚函数法产生的点列为,4. 注意事项,1）初始点x0的选取,使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.,2）惩罚因子初值r0的选取,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同
5、的问题，都要经过多次试算，才能决定一个适当 r0,3) 惩罚因子的缩减系数c的选取,在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为 :,式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。,4). 由于无约束优化问题的解法目前已经有许多很有效的算法，如DFP算法，BFGS法等，所以在求解一些复杂的约束优化问题时，工程技术人员一般乐于采用内点罚函数法。此方法简单、易懂。,5). 尽管外点法和内点法目前都已被广泛应用，但算法中惩罚因子的选取对收敛速度的影响比较大。惩罚因子的
6、增大（外点法）与缩小（内点）使得问题的求解变得很困难，有时甚至会使增广目标函数趋于病态。,一些学者对之,分别提出了混合罚函数法、乘子法。,进行改进，,针对罚函数法这些固有的弱点，,把外点罚函数与内点罚函数结合起来，构造新的罚函数.,三、 混合惩罚函数法,1. 基本思想：,约束,设当前迭代点为,用内点法来构造碰壁项,那些不等式约束和等式约束,按外点法构造惩罚项,即定义混合罚函数为：,构造新的辅助函数,其中：,2. 算法实现,Step2:,得最优解,Step3:,若,否则转Step4,Step1:,给出,误差精度,参数,缩小系数,令,乘子法是由Powell和Hestenes于1969年彼此独立对等
7、式约束的优化问题首次提出来的。,四、 乘子法广义乘子法,1973年，Rockafellar将其推广到不等式约束的优化问题，成为求解约束优化问题的一类重要而有效的方法。,后来，D. A. Bertsekas 对乘子法做了系统的论述与理论分析。与此同时，一些学者给出了乘子法的Fortran程序，使乘子法得到广泛的应用。,把外点罚函数与Lagrange函数结合起来，构造出更合适的新目标函数，使得在罚因子适当大的情况下，借助于Lagrange乘子就能逐步达到原约束问题的最优解。,基本思想：,由于这种方法要借助于Lagrange乘子的迭代进行求解而又区别于经典的Lagrange乘子法，故称为广义乘子法。
8、,1. 等式约束问题的乘子法(Hestenes乘子法),则(1)可等价为：,构造：,可以证明：,用迭代法求出,以上就是乘子法的基本思想,迭代公式为:,并求解,依据：,给定,设对应的无约束问题,即,的最优解为,迭代公式为:,则根据最优解的必要条件知,对照以上两式，,有,于是迭代公式取为:,迭代什么时间终止呢？,等式约束的乘子法,得,例5：,用乘子法求解：,解：,定义增广Lagrange函数如下,取,用解析法解,按公式修正乘子,可见,即分别是所求非线性规划的最优乘子和最优解.,2*.等式约束问题的乘子法(Powell乘子法),Powell在1969年与Hestenes几乎同时，又提出了一种类似的乘
9、子方法：,他考虑含有两组参数的罚函数：,可见，Powell法是一种比Hestenes的方法更广泛一些的乘子法，但两者的出发点不同。,Powell法基于下面的事实。,定理4：,由定理4可知,3. 不等式约束的乘子法(Rockafellar的乘子法),对不等式约束问题,引进辅助变量,上面的问题转化为下面等式约束问题,接下来定义其增广Lagrange函数：,并求其极小.,代入增广的目标函数，有：,接下来就可用求解等式约束情况的方法进行求解了.,相应地, 乘子的迭代公式为：,4. 一般约束情形的乘子法,对于一般约束问题,只要综合等式约束和不等式约束的情况写出增广目标函数来求解即可. 其算法称为PHR算法.,构造广义lagrange函数：,其中,给定初始条件后，求解,按下面指定的公式修正：,PHR算法,本节结束,
