惩罚函数法ppt课件.ppt

《惩罚函数法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.3.4惩罚函数法惩罚函数法简介内点法外点法混合法总结惩罚函数法简介惩罚函数法是一种使用很广泛、很有效的间接法。基本原理：把约束优化问题转化成无约束优化问题来求解。两个前提条件：一是不破坏原约束的约束条件二是最优解必须归结到原约束问题的最优解上去按照惩罚函数的构成方式，惩罚函数法分为三种：外点法、内点法、混合法惩罚函数法简介惩罚项r(k)、m(k)-----罚因子惩罚函数内点法㈠引例设有一维不等式优化问题的数学模型D：几何图形见下页由图可见，目标函数的可行域为x≥b，在可行域内目标函数单调上升，它的最优解

2、显然是x*=b，F*=ab对引例的惩罚函数进行分析，以对内点法有初步认识：⑴本问题是不等式约束优化问题，故只有一项惩罚项，一个罚因子⑵规定罚因子为某一正数，当迭代点是在可行域内时，则惩罚项的值必为正值，因此必有而且，当x越趋近于约束边界时，由于惩罚项增大，所以罚函数的值越大。当x←b时，罚函数的值将趋近于+∞。因此，当初始点取在可行域内，求函数的极小值时，只要适当控制搜索步长，防止迭代点跨入非可行域，则所搜索到的无约束极小点x*必可保持在可行域内。⑶若对于罚因子的取值由初始的逐渐变小时，惩罚函数愈逼近与原目

3、标函数F（x），罚函数曲线越来越接近于原F（x）=ax直线，如上页图，对应罚函数的最优点列不断趋近于原约束优化问题的最优点x*=b小结由以上可见，如果选择一个可行点作初始点，令其罚因子由大变小，同过求罚函数的一系列最优点，显见无约束最优点序列将逐渐趋近于原约束优化问题的最优点x*。㈡内点罚数法的形式及特点⑴具有不等式约束的优化问题的数学模型u=1，2……，p⑵构造如下形式的内点罚函数D：关于惩罚因子规定为正，即。且在优化过程中是减小的，为确保为递减数列，取常数C0

4、罚项，由于在可行域内有，且永远取正值，故在可行域内惩罚项永为正。的值越小则惩罚项的值越小。由于在约束边界上有，因此，当设计点趋于边界时，惩罚项的值将趋于无穷大。由此可知，在可行域内，始终有。当时，却有，所以整个最优化的实质就是用罚函数去逼近原目标函数F(x);当设计点逐渐由内部趋近于边界时，由于惩罚项无穷增大，则称罚函数也将无穷增大。从函数图形上来看，犹如在可行域的边界上筑起一道陡峭的高墙，使迭代点自动保持在可行域内，用此办法来保证搜索过程自始至终不离开可行域。所以，内点法也常称为围墙函数法。⑶内点罚函数法

5、的求解过程为了用惩罚函数去逼近原目标函数F(x)，则要用F(x)及构造一个无约束优化问题的数学模型选取初始点（原约束优化问题的内点），初始罚因子，罚因子降低系数C。用无约束优化方法求上式无约束优化问题的最优解。所得解为；当k在增大的过程中，得到惩罚函数的无约束最优点列为点列中各点均在可行域内部，随着k→∞的过程，点列将趋近于原约束问题的最优解x*。即=x*由此可知，内点法的序列无约束最优点是在可行域内部且趋近于约束最优点x*的。内点罚函数还可以按如下形式构成㈢初始点x(0)的选取由于内点法的搜索是在可行域内

6、进行，显然初始点必须是域内可行点。须满足有两种方法⑴自定法。即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点。⑵搜索法。任选一个设计点为初始点。通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调整，将点逐步引入到可行域内，成为可行初始点，这就是搜索法。㈣关于几个参数的选择⑴初始罚因子r(0)的选取如果值选得太大，则在一开始罚函数的惩罚项的值将远远超出原目标函数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代中，需要很长时间的搜索才能使序列无约束极小点逐渐向约

7、束最优点逼近。如果值选得太小，则在一开始惩罚项的作用甚小，而在可行域内部惩罚函数与原目标函数F(x)很相近，只在约束边界附近罚函数值才突然增高。这样，使其罚函数在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。如下图，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代点进入最优的邻域，以致极易使迭代点落入非可行域而导致计算的失败。r（0）=1~50或⑵递减系数C的选择罚因子递减系数C的选择，一般认为对算法的成败影响不大。规定0

8、但因前后两次无约束最优点之间的距离较远，有可能使后一次无约束优化本身的迭代次数增多，而且使序列最优点的间隔加大，这就对约束最优点的逼近不利。相反，若C值取得较大，则无约束优化次数就要增多。通常建议取C=0.1~0.5㈤终止准则随着罚因子的值不断减小，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。设惩罚函数的无约束最优点列为对应的罚函数值为终止准则可用下述两者之一⑴相邻两次惩罚函数无约束最优点之间的