惩罚函数法

5.3.4惩罚函数法惩罚函数法简介内点法外点法混合法总结惩罚函数法简介惩罚函数法是一种使用很广泛、很有效的间接法。基本原理：把约束优化问题转化成无约束优化问题来求解。两个前提条件：一是不破坏原约束的约束条件二是最优解必须归结到原约束问题的最优解上去按照惩罚函数的构成方式，惩罚函数法分为三种：外点法、内点法、混合法惩罚函数法简介惩罚项r(k)、m(k)-----罚因子惩罚函数内点法㈠引例设有一维不等式优化问题的数学模型D：几何图形见下页由图可见，目标函数的可行域为x≥b，在可行域内目标函数单调上升，它的最优解显然是x*=b，F*=ab对引例的惩罚函数进行分析，以对内点法有初步认识：⑴本问题是不等式约束优化问题，故只有一项惩罚项，一个罚因子⑵规定罚因子为某一正数，当迭代点是在可行域内时，则惩罚项的值必为正值，因此必有而且，当x越趋近于约束边界时，由于惩罚项增大，所以罚函数的值越大。当x←b时，罚函数的值将趋近于+∞。因此，当初始点取在可行域内，求函数的极小值时，只要适当控制搜索步长，防止迭代点跨入非可行域，则所搜索到的无约束极小点x*必可保持在可行域内。⑶若对于罚因子的取值由初始的逐渐变小时，惩罚函数愈逼近与原目标函数F（x），罚函数曲线越来越接近于原F（x）=ax直线，如上页图，对应罚函数的最优点列不断趋近于原约束优化问题的最优点x*=b小结由以上可见，如果选择一个可行点作初始点，令其罚因子由大变小，同过求罚函数的一系列最优点，显见无约束最优点序列将逐渐趋近于原约束优化问题的最优点x*。㈡内点罚数法的形式及特点⑴具有不等式约束的优化问题的数学模型u=1，2……，p⑵构造如下形式的内点罚函数D：关于惩罚因子规定为正，即。且在优化过程中是减小的，为确保为递减数列，取常数C0C1称系数C为罚因子降低系数=0或关于惩罚项，由于在可行域内有，且永远取正值，故在可行域内惩罚项永为正。的值越小则惩罚项的值越小。由于在约束边界上有，因此，当设计点趋于边界时，惩罚项的值将趋于无穷大。由此可知，在可行域内，始终有。当时，却有，所以整个最优化的实质就是用罚函数去逼近原目标函数F(x);当设计点逐渐由内部趋近于边界时，由于惩罚项无穷增大，则称罚函数也将无穷增大。从函数图形上来看，犹如在可行域的边界上筑起一道陡峭的高墙，使迭代点自动保持在可行域内，用此办法来保证搜索过程自始至终不离开可行域。所以，内点法也常称为围墙函数法。⑶内点罚函数法的求解过程为了用惩罚函数去逼近原目标函数F(x)，则要用F(x)及构造一个无约束优化问题的数学模型选取初始点（原约束优化问题的内点），初始罚因子，罚因子降低系数C。用无约束优化方法求上式无约束优化问题的最优解。所得解为；当k在增大的过程中，得到惩罚函数的无约束最优点列为点列中各点均在可行域内部，随着k→∞的过程，点列将趋近于原约束问题的最优解x*。即=x*由此可知，内点法的序列无约束最优点是在可行域内部且趋近于约束最优点x*的。内点罚函数还可以按如下形式构成㈢初始点x(0)的选取由于内点法的搜索是在可行域内进行，显然初始点必须是域内可行点。须满足有两种方法⑴自定法。即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点。⑵搜索法。任选一个设计点为初始点。通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调整，将点逐步引入到可行域内，成为可行初始点，这就是搜索法。㈣关于几个参数的选择⑴初始罚因子r(0)的选取如果值选得太大，则在一开始罚函数的惩罚项的值将远远超出原目标函数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代中，需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。如果值选得太小，则在一开始惩罚项的作用甚小，而在可行域内部惩罚函数与原目标函数F(x)很相近，只在约束边界附近罚函数值才突然增高。这样，使其罚函数在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。如下图，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代点进入最优的邻域，以致极易使迭代点落入非可行域而导致计算的失败。r（0）=1~50或⑵递减系数C的选择罚因子递减系数C的选择，一般认为对算法的成败影响不大。规定0C1。若C值选得较小，罚因子下降快，可以减少无约束优化的次数，但因前后两次无约束最优点之间的距离较远，有可能使后一次无约束优化本身的迭代次数增多，而且使序列最优点的间隔加大，这就对约束最优点的逼近不利。相反，若C值取得较大，则无约束优化次数就要增多。通常建议取C=0.1~0.5㈤终止准则随着罚因子的值不断减小，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。设惩罚函数的无约束最优点列为对应的罚函数值为终止准则可用下述两者之一⑴相邻两次惩罚函数无约束最优点之间的距离已足够的小。设ε1为收敛精度，一般取ε1=10-4~10-5，则需要满足⑵相邻两次惩罚函数值得相对变化量已足够小。设ε2为收敛精度，一般取ε2=10-3~10-4，则需要满足㈥算法步骤⑴构造内点惩罚函数⑵选择可行初始点，初始罚因子，罚因子降低系数C，收敛精度与，置k←0⑶求无约束优化问题，有最优点。⑷当k=0时转步骤⑸，否则转步骤⑹⑸置k←k+1，，并转步骤⑶⑹由终止准则，若满足则转步骤⑺，否则转⑸⑺,输出最优解(x*,F*)内点法流程图给定：x(0)∈D,r(0),C,ε1,ε2k←0K=0?入口用无约束优化方法求罚函数的优化点*kx)(*kxFF1*)0(10)()1(kkxxFFCrrkkkk)(*,***kkxFFxx出口++--200FFF㈦内点罚函数的特点内点法只适用于解不等式约束优化问题。由于内点法需要在可行域内部进行搜索，所以初始点必须在可行域内部选取可行设计点。内点法的突出优点在于每个迭代点都是可行点因此，当迭代达到一定阶段时，尽管尚没有达到最优点，但也可以被接受为一个较好的近似解。外点法外点法可以解不等式约束优化问题或等式约束优化问题㈠引例设有一维不等式优化问题的数学模型D：用外点法构造惩罚函数，具体构造形式如下x≥bxb写成另一种形式如上图，此处的惩罚函数也是由原目标函数F(x)与惩罚项而组成。惩罚项中包含有可调整的参数r(k)与约束函数。由惩罚项的构造可知，若迭代点在可行域的内部，惩罚项的值为0，惩罚函数值与原目标函数值相等；而若在非可行域（即可行域的外部），惩罚项是以约束函数的平方加大的，即迭代点违反约束越严重，惩罚项的值增加的越大。因此，在非可行域内，必有且罚因子r（k）越大，惩罚作用越明显。由图，对于某r(k)值，求出惩罚函数的最优点当取罚因子为递增数列，随k的增加，罚函数的无约束最优点序列为该序列将趋近与原约束问题的最优点x*，x*=b。值得注意的是，尽管增加直至趋于无穷大，但最终的近似最优点x*仍在可行域的外部。即外点法构造的罚函数是使迭代点从可行域的外部逐渐逼近约束最优点，这正是外点法名称的由来。㈡外点罚函数法的形式及特点先讨论解不等式约束优化问题设有不等式约束优化问题u=1，2……，pD：构造外点法惩罚函数的常见形式取正递增引入罚因子递增系数C1，并令=∞惩罚项的含义可用另一形式表示当gu(x)≥0（x∈D）当gu(x)0（x∈D）在可行域内（包括边界）在非可行域，为增函数外点罚函数的求解过程用外点罚函数去逼近原目标函数F(x)，构造一个无约束优化问题模型x∈Rn任选初始点x(0)，初始法罚因子r(0)0,罚因子递增系数C1对于r(k)为某一值，同过对惩罚函数的无约束求优，可得最优点。随着k的增大，得无约束最优点列在k←∞的过程中，点列将趋近于原问题的最优点实线为原目标函数等值线虚线为罚函数等值线总结由上图可见，两种等值线在可行域内部及边界上是重合的；而在非可行域中，罚函数的等值线升高了。即只有在可行域外部惩罚项才起到惩罚的作用。r(k)值越大，惩罚作用越大。由上b图可知，在起作用约束边界处罚函数等值线变得越密集和越陡峭。随r(k)的增大，最优点列将越接近于原约束优化问题的最优点x*。但须注意，近似的最优点是落在边界处非可行域一侧。外点法罚函数常用形式除上面介绍的两种，还有㈢对几个问题的讨论（1）初始点x(0)的选取在可行域及非可行域内均可。（2）初始罚因子r(0)和递增系数C的选取外点法中，这两者的选择对算法的成败和计算速度有显著的影响。见下页图选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，发函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失败。C的选取影响不大，通常C=5~10（3）约束容差带最优点在非可行域内，即位一个非可行点，这对某些工程是不允许的。因此，可在约束边界可行域一侧加一条容差带。相当于将约束条件改为是容差量，通常㈣终止准则随着罚因子的值不断增大，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。设惩罚函数的无约束最优点列为对应的罚函数值为终止准则可用下述两者之一⑴相邻两次惩罚函数无约束最优点之间的距离已足够的小。设ε1为收敛精度，一般取ε1=10-4~10-5，则需要满足⑵相邻两次惩罚函数值得相对变化量已足够小。设ε2为收敛精度，一般取ε2=10-3~10-4，则需要满足外点法流程图给定：x(0)∈R,r(0),C,ε1,ε2k←0k=0?入口用无约束优化方法求罚函数的优化点*kx)(*kxFF1*)0(10)()1(kkxxFFCrrkkkk)(*,***kkxFFxx出口++--㈣算法步骤与流程图200FFF⑶求，得最优点⑷当k=0时转步骤⑸，否则转步骤⑹⑸置k←k+1，，并转步骤⑶⑹由终止准则，若满足则转步骤⑺，否则转⑸⑺,输出最优解(x*,F*)，停止计算。算法步骤⑴在n维空间任取初始点x（0）⑵选取初始罚因子r(0),递增系数C，并置k←0㈤用外点罚函数法解等式约束优化问题设有二维约束优化问题D：h1(x)=x1+x2-10=0如右图，h1（x）为该约束问题的可行域，这条直线以外的整个x1ox2平面为非可行域。目标函数等值线与该直线的切点为最优点最优点按外点法的基本思想，构造惩罚函数x∈Dx∈D在可行域上，惩罚项的值为零，惩罚函数值与原目标函数值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于原目标函数，即在可行域外惩罚项起到了惩罚作用。在k←∞的过程中，点列将趋近于原问题的最优点对于m(k)，随着k的增大，得无约束最优点列推广到具有一般的等式约束优化问题D：首先构造如下形式的外点惩罚函数惩罚因子m（k）规定取正，m(0)m(1)……。即罚因子递增系数C0在可行域上值为零，非可行域上，值恒大于零混合法用罚函数法解决有等式约束和不等式约束的一般约束（GP型）优化问题的方法，把它称为混合惩罚函数法，简称混合法。1混合法惩罚函数的形式及特点一般约束问题的优化模型D：用惩罚函数法将其转化为无约束优化问题惩罚函数是由原目标函数及包含约束函数的惩罚项组成。由于该问题的约束条件包含不等式约束与等式约束两部分。因此，惩罚项也应由对应的两部分组成。对应等式约束部分的只有外点法一种形式，而对应不等式的约束部分有内点法或外点法两种形式。因此按照对不等式约束处理的方法不同，混合法惩罚函数也具有两种形式。⑴内点形式的混合法不等式约束部分按内点法形式处理的混合法，惩罚函数形式为是递增序列为了统一用一个罚因子r（k），且又按内点法形式，即0C1上式可写为⑵外点形式的混合法不等式约束部分按外点法形式处理的混合法，惩罚函数形式为其中，罚因子r（k）恒为正，且为递增序列，即递增系数C1初始点可在Rn空间内任选，初始罚因子及递增系数参照外点法选取。2算法步骤及流程图参照内点法与外点法。（外点法，内点法）例题设有二维一般约束优化问题，数学模型为D：目标函数等值线及约束曲线见下图。最优点x*既要在不等式约束包括的范围内，同时又必须在等式约束h(x)=0的直线上，试求该