第五章 惩罚函数法.ppt

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

2、行分析，以对内点法有初步认识：,本问题是不等式约束优化问题，故只有一项惩罚项 ，一个罚因子,规定罚因子 为某一正数，当迭代点是在可行域内 时，则惩罚项的值必为正值，因此必有,而且，当x越趋近于约束边界时，由于惩罚项,增大，所以罚函数 的值越大。当xb时，罚函 数的值将趋近于+。因此，当初始点取在可行域内，求 函数 的极小值时，只要适当控制搜索步长， 防止迭代点跨入非可行域，则所搜索到的无约束极小点 x*必可保持在可行域内。,若对于罚因子的取值由初始的 逐渐变小 时，惩罚函数 愈逼近于原目标函数F（x），罚 函数曲线越来越接近于原F（x）=ax直线，如图所示，对 应罚函数 的最优点列 不断趋近于

3、原约 束优化问题的最优点x*=b,小结,由以上可见，如果选择一个可行点作初始点 ，令其罚因子 由大变小，通过求罚函数 的一系列最优点， 显见，无约束最优点序列将逐渐趋近于原约束优化问题的最优点x*。,内点罚数法的形式及特点,具有不等式约束的优化问题的数学模型,u=1，2，p,构造如下形式的内点罚函数,S.T. :,关于惩罚因子规定为正，即 。且在优化过程中 是减小的，为确保为递减数列，取常数C,0C1,称系数C为罚因子降低系数,=0,或,关于惩罚项 ，由于在可行域内有 ， 且 永远取正值，故在可行域内惩罚项永为正。 的值越小则惩罚项的值越小。,由于在约束边界上有 ，因此，当设计点趋 于边界时，

4、惩罚项的值将趋于无穷大。由此可知，在可 行域内，始终有 。,当 时 ，却有 ，所以整个最 优化的实质就是用罚函数 去逼近原目标函数F(x); 当设计点逐渐由内部趋近于边界时，由于惩罚项无穷 增大，则罚函数也将无穷增大。,从函数图形上来看，犹如在可行域的边界上筑起一 道陡峭的高墙，使迭代点自动保持在可行域内，用此办 法来保证搜索过程自始至终不离开可行域。所以，内点法 也常称为围墙函数法。,内点罚函数法的求解过程,为了用惩罚函数 去逼近原目标函数F(x)， 则要用F(x)及 构造一个无约束优化问题的数学模型,选取初始点（原约束优化问题的内点） ，初始罚 因子 ，罚因子降低系数C。用无约束优化方法求

5、上式无 约束优化问题的最优解。,所得解为 ；当k在增大的过程中，得到惩罚函数的无 约束最优点列为,点列中各点均在可行域内部，随着k的过程， 点列将趋近于原约束问题的最优解x*。即,=x*,由此可知，内点法的序列无约束最优点 是在可行域内 部且趋近于约束最优点x*的。,内点罚函数还可以按如下形式构成,初始点x(0)的选取,由于内点法的搜索是在可行域内进行，显然初始点必须 是域内可行点。须满足,确定初始点常用如下两种方法,自定法 即根据设计者的经验或已有的计算资料自行决 定某一可行点作为初始点。,搜索法 任选一个设计点 为初始点。通过对初始点 约束函数值的检验，按其对每个约束的不满足程度加以调 整

6、，将 点逐步引入到可行域内，成为可行初始点， 这就是搜索法。,关于几个参数的选择,初始罚因子r(0)的选取,如果 值选得太大，则在一开始罚函数的惩罚项的 值将远远超出原目标函数的值，因此，它的第一次无约束极 小点将远离原问题的约束最优点。在以后的迭代中，需要很 长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。,如果 值选得太小，则在一开始惩罚项的作用甚小， 而在可行域内部惩罚函数 与原目标函数F(x)很相近， 只在约束边界附近罚函数值才突然增高。这样，使其罚函数 在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。,如下图，对于有深沟谷地性态差的函数，不仅搜索所需的 时间长，而且很难使

7、迭代点进入最优的邻域，以致极易使 迭代点落入非可行域而导致计算的失败。,r（0）=150,或,递减系数C的选择,罚因子递减系数C的选择，一般认为对算法的成败影响 不大。规定0C1。,若C值选得较小，罚因子下降快，可以减少无约束优化 的次数，但因前后两次无约束最优点之间的距离较远，有 可能使后一次无约束优化本身的迭代次数增多，而且使序 列最优点的间隔加大，对约束最优点的逼近不利。,相反，若C值取得较大，则无约束优化次数就要增多。,通常建议取C=0.1-0.5,终止准则,随着罚因子 的值不断减小，罚函数的序列无约 束最优点将越来越趋近于原约束优化问题的最优点。,设惩罚函数 的无约束最优点列为,对应

8、的罚函数值为,终止准则可用下述两者之一,相邻两次惩罚函数无约束最优点之间的距离已足够的小。,设1为收敛精度，一般取1=10-4-10-5，则需要满足,相邻两次惩罚函数值的相对变化量已足够小。,设2为收敛精度，一般取2=10-3-10-4，则需要满足,算法步骤,构造内点惩罚函数,选择可行初始点 ，初始罚因子 ，罚因子降低系 数C，收敛精度 与 ，置k0,求无约束优化问题， 有最优点 。,当k=0时转步骤，否则转步骤,置kk+1， ，并转步骤,由终止准则，若满足则转步骤，否则转, , 输出最优解(x*,F*),内点法流程图,给定：x(0) D,r(0),C,1,2,k0,K=0?,入口,用无约束优

9、化方法求罚函数 的优化点,出口,+,+,-,-,内点罚函数的特点,内点法只适用于解不等式约束优化问题。由于内点法 需要在可行域内部进行搜索，所以初始点必须在可行域 内部选取可行设计点。,内点法的突出优点在于每个迭代点都是可行点,因此，当迭代达到一定阶段时，尽管尚没有达到最优点， 但也可以被接受为一个较好的近似解。,5.3.4.2 外点法,外点法可以解不等式约束优化问题或等式约束优化问题,引例 设有一维不等式优化问题的数学模型,用外点法构造惩罚函数，具体构造形式如下,xb,xb,S.T. :,写成另一种形式,如上图，此处的惩罚函数也是由原目标函数F(x)与惩罚 项而组成。惩罚项中包含有可调整的参

10、数r(k)与约束函数。,由惩罚项的构造可知，若迭代点在可行域的内部，惩罚 项的值为0，惩罚函数值与原目标函数值相等；而若在非可 行域（即可行域的外部），惩罚项是以约束函数的平方加 大的，即迭代点违反约束越严重，惩罚项的值增加的越大。 因此，在非可行域内，必有 且罚因子r（k）越 大，惩罚作用越明显。,由图，对于某r(k)值，求出惩罚函数 的最优点 当取罚因子 为递增数列，随k的增加，罚函数的无约束最 优点序列为,该序列将趋近与原约束问题的最优点x*，x*=b。 值得注意的是，尽管 增加直至趋于无穷大，但最终 的近似最优点x*仍在可行域的外部。 即外点法构造的罚函数是使迭代点从可行域的外部逐 渐

11、逼近约束最优点，这正是外点法名称的由来。,外点罚函数法的形式及特点,先讨论解不等式约束优化问题,设有不等式约束优化问题,u=1，2，p,构造外点法惩罚函数的常见形式,取正递增,S.T. :,引入罚因子递增系数C1，并令,=,惩罚项,的含义可用另一形式表示,当gu(x) 0 （xD）,当gu(x) 0 （xD）,在可行域内 （包括边界）,在非可行域， 为递增函数,外点罚函数的求解过程,用外点罚函数去逼近原目标函数F(x)，构造一个无约束 优化问题模型,xRn,任选初始点x(0)，初始法罚因子r(0)0,罚因子递增系数C1,对于r(k)为某一值，同过对惩罚函数的无约束求优，可 得最优点 。随着k的

12、增大，得无约束最优点列,在k的过程中，点列将趋近于原问题的最优点,实线为原目标 函数等值线,虚线为罚函数 等值线,总结,由上图可见，两种等值线在可行域内部及边界上是重合 的；而在非可行域中，罚函数的等值线升高了。即只有在 可行域外部惩罚项才起到惩罚的作用。r(k)值越大，惩罚作 用越大。,由上b图可知，在起作用约束边界处罚函数等值线变得越 密集和越陡峭。随r(k)的增大，最优点列将越接近于原约束 优化问题的最优点x*。但须注意，近似的最优点是落在边 界处非可行域一侧。,对几个问题的讨论,（1）初始点x(0)的选取,在可行域及非可行域内均可。,（2）初始罚因子r(0)和递增系数C的选取,外点法中

13、，这两者的选择对算法的成败和计算速度有显著 的影响。,选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，发函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失 败。,C的选取影响不大，通 常C=5-10,（3）约束容差带,最优点在非可行域内，是一个非可行点，这对某些工 程是不允许的。因此，可在约束边界可行域一侧加一条容 差带。,相当于将约束条件改为,是容差量，通常,终止准则,随着罚因子 的值不断增大，罚函数的序列无约束最 优点将越来越趋近于原约束优化问题的最优点。,设惩罚函数 的无约束最优点列为,对应的罚

14、函数值为,终止准则可用下述两者之一,相邻两次惩罚函数无约束最优点之间的距离已足够的小。,设1为收敛精度，一般取1=10-4-10-5，则需要满足,相邻两次惩罚函数值的相对变化量已足够小。,设2为收敛精度，一般取2=10-3-10-4，则需要满足,外点法流程图,给定：x(0) R ,r(0),C,1,2,k0,k=0?,入口,用无约束优化方法求罚函数 的优化点,出口,+,+,-,-,算法步骤与流程图,求 ，得最优点,当k=0时转步骤，否则转步骤,置kk+1， ，并转步骤,由终止准则，若满足则转步骤，否则转, , 输出最优解(x*,F*)，停止计算。,算法步骤,在n维空间任取初始点x（0）,选取初

15、始罚因子r(0),递增系数C，并置k0,用外点罚函数法解等式约束优化问题,设有二维约束优化问题,h1(x)=x1+x2-10=0,如右图，h1(x)为该约束 问题的可行域，这条直线以 外的整个x1ox2平面为非可 行域。目标函数等值线与该 直线的切点为最优点,最优点,S.T. :,按外点法的基本思想，构造惩罚函数,xD,xD,在可行域上，惩罚项的值为零，惩罚函数值与原目标函数 值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于 原目标函数，即在可行域外惩罚项起到了惩罚作用。,在k的过程中，点列将趋近于原问题的最优点,对于m(k)，随着k的增大，得无约束最优点列,推广到具有一般的等式约束优化问

16、题,首先构造如下形式的外点惩罚函数,惩罚因子m（k）规定取正，m(0)1,在可行域上值为零，非可行域上，值恒大于零,S.T. :,5.3.4.3 混合法,用罚函数法解决有等式约束和不等式约束的一般约束 （GP型）优化问题的方法，把它称为混合惩罚函数法， 简称混合法。,1 混合法惩罚函数的形式及特点,一般约束问题的优化模型,S.T. :,用惩罚函数法将其转化为无约束优化问题,惩罚函数是由原目标函数及包含约束函数的惩罚项组 成。由于该问题的约束条件包含不等式约束与等式约束 两部分。因此，惩罚项也应由对应的两部分组成。对应 等式约束部分的只有外点法一种形式，而对应不等式 的约束部分有内点法或外点法两

17、种形式。因此按照对不 等式约束处理的方法不同，混合法惩罚函数也具有两种 形式。,内点形式的混合法,不等式约束部分按内点法形式处理的混合法，惩罚函数 形式为,是递增序列,为了统一用一个罚因子r（k），且又按内点法形式，即,0C1,上式可写为,外点形式的混合法,不等式约束部分按外点法形式处理的混合法，惩罚函数 形式为,其中，罚因子r(k)恒为正，且为递增序列，即,递增系数C1,初始点可在Rn空间内任选，初始罚因子及递增系数参照 外点法选取。,2 算法步骤及流程图,参照内点法与外点法。（外点法，内点法）,例题,设有二维一般约束优化问题，数学模型为,S.T. :,目标函数等值线及约束曲线见下图。,最优点x*既要在不等式 约束包括的范围内，同时 又必须在等式约束 h(x)=0 的直线上，试求该约束优化