约束优化方法.ppt

约束优化方法,约束优化方法概述约束优化问题的最优解及其必要条件约束坐标轮换法约束随机方向法复合形法惩罚函数法教学要求：1、掌握约束优化局部最优解的必要条件。2、掌握复合形法得原理及程序设计。3、掌握内点法和外点法的惩罚函数的构造原理及程序设计。,约束优化方法概述,无约束优化方法是优化方法中最基本最核心的部分。在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。一、约束优化问题的类型 根据约束条件类型的不同可以分为三种，其数学模型分别如下：1、不等式约束优化问题（IP型）,2、等式约束优化问题（EP型）3、一般约束优化问题（GP型）,二、约束优化方法的分类约束优化方法按求解原理的不同可以分为直接法和间接法两类。1、直接法 只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。其基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。,适用性：当前迭代点的目标函数值较前一点是下降的，即满 F(xk+1)F(xk),可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x)0,u=1,2,p,2、间接法 该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法,5.1约束优化问题的最优解及其必要条件,5.1.1局部最优解与全局最优解 对于具有不等式约束的优化问题，若目标函数是凸集上的凸函数，则局部最优点就是全局最优点。如左图所示，无论初始点选在何处，搜索将最终达到唯一的最优点。否则，目标函数或可行域至少有一个是非凸性的，则可能出现两个或更多个局部最优点，如右图所示，此时全局最优点是全部局部最优点中函数值最小的一个。,对于具有等式约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小的一个。对于具有一般约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小且同时满足等式约束与不等式约束的一个。例如：设数学模型为,该优化问题的最优点如下图所示，对于这两个局部最小点 x1*=-1 0 T,x2*=5 0 T，其函数值不同，F(x1*)=4,F(x2*)=16。全局最优点为 x1*=-1 0 T F*=4,h(x),h(x),g(x),x1*,x2*,x1,x2,2,4,6,-2,5.1.2 起作用约束与不起作用约束 对于一般约束优化问题，其约束分为两类：等式约束和不等式约束。在可行设计点x(k)处，对于不等式约束，若gi(x(k)=o，则称第i个约束gi(x)为可行点的起作用约束；否则，若gi(x(k)o，则称gi(x)为可行点的不起作用约束。即只有在可行域的边界上的点才有起作用约束，所有约束对可行域内部的点都是不起作用约束。对于等式约束，凡是满足该约束的任一可行点，该等式约束都是起作用约束。,5.2 约束优化问题极小点的条件 约束优化问题极小点的条件，是指在满足约束条件下，目标函数局部极小点的存在条件。约束问题最优解的存在条件有两种：一是极小点在可行域内部，二是极小点在可行域的一个或几个边界交汇处。5.2.1 不等式约束问题解的必要条件 第一种情况：如图所示，g1(x*)=0，g2(x*)0，g3(x*)0。所以g1(x)为起作用约束，g2(x)、g3(x)为不起作用约束。由于约束最优点是目标函数与约束g1(x)边界的切点，故目标函数与约束函数的梯度必共线，而且方向一致。,2、在可行设计点x(k)处，起作用约束在该点的邻域内不但起限制可行域范围的作用，而且还可以提供可行搜索方向的信息。3、由于约束最优点一般发生在起作用约束上，不起作用约束在求解最优点的过程中，可以认为是无任何影响，所以可以略去不起作用约束，把所有起作用约束当作等式约束问题求解最优点。,1、约束优化问题的最优解不仅与目标函数有关，而且与约束集合的性质有关。,若取非负乘子1*0，则在x*处存在如下关系 F(x*)-1*g1(x*)=0,x*,g1(x*),g3(x),F(x*),g1(x),g2(x),第二种情况：如图所示，若最优点位于两约束的交点上，则目标函数的梯度矢量夹于两约束函数梯度矢量之间。则目标函数的梯度可以表示为约束函数梯度的线性组合，若取非负乘子1*0，2*0，则在x*处存在如下关系 F(x*)=1*g1(x*)+2*g2(x*),g1(x*),g2(x*),g2(x),g1(x),F(x*),结论：对于不等式约束优化问题，其最优解的必要条件为,5.2.2 等式约束问题解的必要条件 如图所示，目标函数梯度矢量与约束函数梯度矢量共线。因此，一定存在一个乘子，使得下式成立：F(x*)-*h(x*)=0 对于一般等式约束优化问题，其最优解必要条件为,x*,h(x)=0,F(x*),h(x*),5.2.3 一般约束问题解的必要条件 由上述不等式约束优化与等式约束优化问题解的必要条件，可以推出一般约束优化问题最优解的条件：,5.2.4 库恩-塔克条件 在优化实用计算中，为判断可行迭代点是否是约束最优点，或者对输出的可行结果进行检查，观察其是否满足约束最优解的必要条件，引入库恩-塔克条件。u v称为拉格朗日乘子 上式也称为约束优化问题局部最优点的必要条件。,在迭代点 处展开式的形式为,一般情况下，其作用约束数J不大于问题的维数,其中 是待定系数矢量,解上式，得一组j（j=1，2J），如果j（j=1，2J）均为非负，标志 满足K-T条件。该条件是 为极小点的必要条件。,如果点 是最优点，则必须满足K-T条件；反之，满足K-T条件的点则不一定是约束最优点。,只有当目标函数是凸函数，约束构成的可行域是凸集时，则满足K-T条件的点 是全局极小点的必要而充分条件。,讨论:约束最优解的必要条件几何条件,当迭代点 有两个起作用约束，写出目标函数与约束集的关系如下：,最优点,非最优点,区域内,区域外,例题5.1 设约束优化问题,D：,它的当前迭代点为，试用K-T条件判别它是否为约束最优点。,解：计算 点的诸约束函数值,点的起作用约束是,求 点的诸梯度,求拉格朗日乘子,按K-T条件应有,写成线性方程组,解得,乘子均为非负，满足约束最优解一阶必要条件,得,上题图,5.3.1 约束坐标轮换法,一、约束坐标轮换法与无约束坐标轮换法的区别 约束坐标轮换法的基本思想与无约束坐标轮换法基本相同，其主要区别如下：1、沿坐标方向搜索的迭代步长采用加速步长，而不是采用最优步长。因为按照最优步长所得到的迭代点往往超出了可行域。2、对于每一个迭代点，不仅要检查目标函数值是否下降，而且必须检查是否在可行域内，即进行适用性和可行性的检查。,5.3 常用约束优化方法,约束坐标轮换法,一 方法概要述,首先在可行域D内任取一初始点，并取迭代精度。,以 为起点，取一个适当的初步步长 按迭代式,取得沿x1坐标轴正向的第一个迭代点，检查该点的适用性和可行性，即检查,如果两者均满足，则步长加倍,再按迭代式,获得沿x1正向的第二个迭代点。下面的各次迭代，只要对新迭代点的适用性和可行性的检查都通过，再倍增步长后按迭代式,不断产生新迭代点,但是，当迭代点到达 时，该点已违反了可行性条件，于是返回到前一迭代点 作为沿e1方向搜索的终点。,转而改沿x2坐标轴正向进行搜索。在图示情况下，正向的第一个迭代点目标函数值增加，即不再满足适用性条件，故改取该坐标轴的反方向，并取步长 进行迭代，,以后的迭代方向与前述的相同，以加速步长继续迭代，直到至少违反适用性与可行性条件之一时，可确定沿e2方向的迭代终点。,如此反复的进行各坐标轴方向的迭代，点列将逐步逼近最优点x*。,当迭代点到达，如出现下面的情况：,不论沿e1或e2正，反方向以步长 进行搜索，所得 邻近的四个点 当他们都不能同时满足适用性和可行性条件时，此 即可作为约束最优点输出。如果要获得精度更高些的解，还可以缩减初始步长。后在继续迭代，直至 时，才输出最优点，并停止计算。,约束坐标轮换法算法明了、迭代简单、便于掌握和运用。但是其收敛速度较慢，而且在某些情况下，会出现“死点”。如上图中的点 xk，该点已经逼近约束边界，其后的迭代点无论沿何方向，都不可能同时满足适用性及可行性的要求。故xk点作为最优解输出，但显然它就是一个伪最优点。为辨别输出最优点的真伪，可以用K-T条件检验。,5.3.2 随机方向法,参看右图,预先选定可行初始点，利用随机函数构成随机方向S1，按给定的初始步长，沿S1方向取得试探点,检查x点的适用性和可行性,若满足,继续按下面的迭代式在S1方向上获取新点。重复上述步骤，迭代点可沿S1方向前进。直至到达某迭代点不能同时满足适用性和可行性条件时结束。退回到前一点作为该方向搜索中的最终成功点，记作。,将 作为新的起点 再产生另一随机方向S2，以步长 重复以上过程，得到沿S2方向的最终成功点。如此循环，点列必将逼近于约束最优点x*。,若在某个换向转折处，沿某随机方向的试探点目标函数值增大或者越出可行域，则弃去该方向，再产生另一随机方向作试探。试探成功就前进，否则，重新产生新随机方向。,约束随机方向法的搜索方向比坐标轮换法要灵活多。当预定的随机方向限定数M足够大时它不会像坐标轮换法那样出现“病态”而导致输出伪最优点。,当在某个转折点处沿M个随机方向试探均失败，如图中点，则说明以此点为中心，为半径的圆周上M个点都不是适用且可行的点。此时，可将初始步长 缩半后继续试探。直到，且沿M个随机方向都试探失败时，则最后一个成功点就是达到预定精度要求的约束最优点，迭代即可结束。,M是预先规定的在某转折点处产生随机方向所允许的最大数目。一般在50-500范围内选取。对于性态不好的目标函数或可行域有狭长弯道的问题，M应取较大值。,5.3.3 复合形法,复合形法是求解约束优化问题的一种重要的直接解法。一、复合形法的基本思想 基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点,并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。,引例：设有一约束优化的模型为,D：,该问题的目标函数见下图,目标函数等直线和可行域的几何描述,迭代过程,二、初始复合形的构成 要构成初始复合形，实际上就是确定k个可行点作为复合形的顶点，顶点数目一般在n+1 k 2n范围内。对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。为此，提出构成复合形的随机方法。该方法是先产生k个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都成为可行点而构成初始复合形。,构成复合形的随机方法：1、产生k个随机点 利用标准随机函数产生在（0，1）区间内均匀分布的随机数i，然后产生区间（ai，bi）内的随机变量xi，xi=ai+i（bi-ai），i=1，2，n。以这n个随机变量为坐标构成随机点x,第一个点记作x(i)同理，再次产生在（0，1）区间内均匀分布的随机数i，然后获得区间（ai，bi）内的随机点x(2)，依次类推，可以获得k个随机点 x(1)、x(2)、x(3)、.、x(k)。可以看出，产生k个随机点总共需要产生kn个随机数。,2、将非可行点移入可行域 用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果k个随机点没有一个是可行点，则应重新产生随机点，直至其中有至少一个是可行点为止。将非可行点移入可行域的方法：依次检查随机点x(1)、x(2)、x(3)、.、x(k)的可行性。将查出的第一个可行点x(j)与x(1)对调，则新的x(1)点为可行点，然后检查随后的各点是否是可行点，若某点属于可行域，继续检查，直至出现不属于可行域的随机点，然后把此点移入可行域内。,若已知k个随机顶点中前面q个点都是可行点，而x(q+1)为非可行点，则将x(q+1)移入可行域的步骤为：(1)计算q个点的点集中心x(s).(2)将第q+1个点朝x(s)点方向移动，并按下式产生新的点，x(p)=x(s)+0.5(x(q+1)-x(s)此点实际上是x(s)与x(q+1)两点的连线的中点。若新点仍为非可行点，则按上式再产生一个新点，直至 x(p)成为可行点为止。,将非可行点调入可行域,3、构成初始复合形 将全部顶点变为可行点后，就构成了可行域内的初始复合形。三、复合形法的迭代步骤 1、构成初始复合形 2、计算k个顶点函数值F(x(j),j=1,2,k，并选出好点x(L)与坏点x(H)。x(L):F(x(L)=minF(x(j),j=1,2,k x(H):F(x(H)=maxF(x(j),j=1,2,k 3、计算除坏点外其余各点的中心点x0,4、计算映射点x(R)x(R)=x0+(x0-x(H)通常取=1.3，检查x(R)是否在可行域，若为非可行点，将映射系数缩半并重新计算映射点，直到进入可行域。,5、构成新复合形 计算映射点与坏点的目标函数值并进行比较，若（1）映射点优于坏点，即F(x(R)F(x(H)，可用缩半映射系数的方法把映射点拉近。但也有可能经过多次的减半,直到小于给定的很小正数时仍不能使映射点优于坏点,则说明该映射方向不利.改变映射方向,取对次坏点 x(SH):F(x(SH)=maxF(x(j),j=1,2,k,jH 的映射.确定不包括x(SH)在内的复合形顶点中心,并以此为映射轴心,计算x(SH)的影射点x(R)x(R)=x0+(x0-x(SH),6、判定终止条件 复合形在逼近最优点的过程中，当复合形缩得很小时，各顶点的目标函数值必然非常接近。故常用以下终止条件。（1）各顶点与好点的函数值之差的均方根小于误差限，即（2）各顶点与好点的函数值之差的平方和小于误差限，即,3）各顶点与好点的函数值之差的绝对值之和小于误差限，即若不满足终止条件，返回步骤2，否则，可将复合形得好点及其函数值作为最优解输出。,四、讨论 在用直接法解决约束优化问题时，复合形法是一种效果较好的方法。这种方法不需要计算目标函数的导数，也不进行一维搜索，因此对目标函数和约束函数无特殊要求，适用范围广，编程简单。但是收敛速度较慢，不能用于解决具有等式约束的优化问题。,5.3.4 惩罚函数法,惩罚函数法简介内点法外点法混合法总结,惩罚函数法简介,惩罚函数法是一种使用很广泛、很有效的间接法。,基本原理：把约束优化问题转化成无约束优化问题来求解。两个前提条件：一是不破坏原约束的约束条件二是最优解必须归结到原约束问题的最优解上去,按照惩罚函数的构成方式，惩罚函数法分为三种：外点法、内点法、混合法,惩罚函数法简介,惩罚项,r(k)、m(k)-罚因子,惩罚函数,内点法,引例 设有一维不等式优化问题的数学模型,D：,几何图形见下页,由图可见，目标函数的可行域为xb，在可行域内目标函数单调上升，它的最优解显然是,x*=b，F*=ab,对引例的惩罚函数进行分析，以对内点法有初步认识：,本问题是不等式约束优化问题，故只有一项惩罚项，一个罚因子,规定罚因子 为某一正数，当迭代点是在可行域内时，则惩罚项的值必为正值，因此必有,而且，当x越趋近于约束边界时，由于惩罚项,增大，所以罚函数 的值越大。当xb时，罚函数的值将趋近于+。因此，当初始点取在可行域内，求函数 的极小值时，只要适当控制搜索步长，防止迭代点跨入非可行域，则所搜索到的无约束极小点x*必可保持在可行域内。,若对于罚因子的取值由初始的 逐渐变小 时，惩罚函数 愈逼近与原目标函数F（x），罚函数曲线越来越接近于原F（x）=ax直线，如上页图，对应罚函数 的最优点列 不断趋近于原约束优化问题的最优点x*=b,小结,由以上可见，如果选择一个可行点作初始点，令其罚因子 由大变小，同过求罚函数 的一系列最优点，显见无约束最优点序列 将逐渐趋近于原约束优化问题的最优点x*。,内点罚数法的形式及特点,具有不等式约束的优化问题的数学模型,u=1，2，p,构造如下形式的内点罚函数,D：,关于惩罚因子规定为正，即。且在优化过程中 是减小的，为确保为递减数列，取常数C,0C1,称系数C为罚因子降低系数,=0,或,关于惩罚项，由于在可行域内有，且 永远取正值，故在可行域内惩罚项永为正。的值越小则惩罚项的值越小。,由于在约束边界上有，因此，当设计点趋于边界时，惩罚项的值将趋于无穷大。由此可知，在可行域内，始终有。,当 时，却有，所以整个最优化的实质就是用罚函数 去逼近原目标函数F(x);当设计点逐渐由内部趋近于边界时，由于惩罚项无穷增大，则称罚函数也将无穷增大。,从函数图形上来看，犹如在可行域的边界上筑起一道陡峭的高墙，使迭代点自动保持在可行域内，用此办法来保证搜索过程自始至终不离开可行域。所以，内点法也常称为围墙函数法。,内点罚函数法的求解过程,为了用惩罚函数 去逼近原目标函数F(x)，则要用F(x)及 构造一个无约束优化问题的数学模型,选取初始点（原约束优化问题的内点），初始罚因子，罚因子降低系数C。用无约束优化方法求上式无约束优化问题的最优解。,所得解为；当k在增大的过程中，得到惩罚函数的无约束最优点列为,点列中各点均在可行域内部，随着k的过程，点列将趋近于原约束问题的最优解x*。即,=x*,由此可知，内点法的序列无约束最优点 是在可行域内部且趋近于约束最优点x*的。,内点罚函数还可以按如下形式构成,初始点x(0)的选取,由于内点法的搜索是在可行域内进行，显然初始点必须是域内可行点。须满足,有两种方法,自定法。即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点。,搜索法。任选一个设计点 为初始点。通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调整，将 点逐步引入到可行域内，成为可行初始点，这就是搜索法。,关于几个参数的选择,初始罚因子r(0)的选取,如果 值选得太大，则在一开始罚函数的惩罚项的值将远远超出原目标函数的值，因此，它的第一次无约束极小点将远离原问题的约束最优点。在以后的迭代中，需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近。,如果 值选得太小，则在一开始惩罚项的作用甚小，而在可行域内部惩罚函数 与原目标函数F(x)很相近，只在约束边界附近罚函数值才突然增高。这样，使其罚函数在在约束边界附近出现深沟谷地，罚函数的性态变得恶劣。,如下图，对于有深沟谷地性态差的函数，不仅搜索所需的时间长，而且很难使迭代点进入最优的邻域，以致极易使迭代点落入非可行域而导致计算的失败。,r（0）=150,或,递减系数C的选择,罚因子递减系数C的选择，一般认为对算法的成败影响不大。规定0C1。,若C值选得较小，罚因子下降快，可以减少无约束优化的次数，但因前后两次无约束最优点之间的距离较远，有可能使后一次无约束优化本身的迭代次数增多，而且使序列最优点的间隔加大，这就对约束最优点的逼近不利。,相反，若C值取得较大，则无约束优化次数就要增多。,通常建议取C=0.10.5,终止准则,随着罚因子 的值不断减小，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。,设惩罚函数 的无约束最优点列为,对应的罚函数值为,终止准则可用下述两者之一,相邻两次惩罚函数无约束最优点之间的距离已足够的小。,设1为收敛精度，一般取1=10-410-5，则需要满足,相邻两次惩罚函数值得相对变化量已足够小。,设2为收敛精度，一般取2=10-310-4，则需要满足,算法步骤,构造内点惩罚函数,选择可行初始点，初始罚因子，罚因子降低系数C，收敛精度 与，置k0,求无约束优化问题，有最优点。,当k=0时转步骤，否则转步骤,置kk+1，并转步骤,由终止准则，若满足则转步骤，否则转,输出最优解(x*,F*),内点法流程图,给定：x(0)D,r(0),C,1,2,k0,K=0?,入口,用无约束优化方法求罚函数的优化点,出口,+,+,-,-,内点罚函数的特点,内点法只适用于解不等式约束优化问题。由于内点法需要在可行域内部进行搜索，所以初始点必须在可行域内部选取可行设计点。,内点法的突出优点在于每个迭代点都是可行点,因此，当迭代达到一定阶段时，尽管尚没有达到最优点，但也可以被接受为一个较好的近似解。,外点法,外点法可以解不等式约束优化问题或等式约束优化问题,引例 设有一维不等式优化问题的数学模型,D：,用外点法构造惩罚函数，具体构造形式如下,xb,xb,写成另一种形式,如上图，此处的惩罚函数也是由原目标函数F(x)与惩罚项而组成。惩罚项中包含有可调整的参数r(k)与约束函数。,由惩罚项的构造可知，若迭代点在可行域的内部，惩罚项的值为0，惩罚函数值与原目标函数值相等；而若在非可行域（即可行域的外部），惩罚项是以约束函数的平方加大的，即迭代点违反约束越严重，惩罚项的值增加的越大。因此，在非可行域内，必有 且罚因子r（k）越大，惩罚作用越明显。,由图，对于某r(k)值，求出惩罚函数 的最优点 当取罚因子 为递增数列，随k的增加，罚函数的无约束最优点序列为,该序列将趋近与原约束问题的最优点x*，x*=b。值得注意的是，尽管 增加直至趋于无穷大，但最终 的近似最优点x*仍在可行域的外部。即外点法构造的罚函数是使迭代点从可行域的外部逐渐逼近约束最优点，这正是外点法名称的由来。,外点罚函数法的形式及特点,先讨论解不等式约束优化问题,设有不等式约束优化问题,u=1，2，p,D：,构造外点法惩罚函数的常见形式,取正递增,引入罚因子递增系数C1，并令,=,惩罚项,的含义可用另一形式表示,当gu(x)0（xD）,当gu(x)0（xD）,在可行域内（包括边界）,在非可行域，为增函数,外点罚函数的求解过程,用外点罚函数去逼近原目标函数F(x)，构造一个无约束优化问题模型,xRn,任选初始点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=510,（3）约束容差带,最优点在非可行域内，即位一个非可行点，这对某些工程是不允许的。因此，可在约束边界可行域一侧加一条容差带。,相当于将约束条件改为,是容差量，通常,终止准则,随着罚因子 的值不断增大，罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点。,设惩罚函数 的无约束最优点列为,对应的罚函数值为,终止准则可用下述两者之一,相邻两次惩罚函数无约束最优点之间的距离已足够的小。,设1为收敛精度，一般取1=10-410-5，则需要满足,相邻两次惩罚函数值得相对变化量已足够小。,设2为收敛精度，一般取2=10-310-4，则需要满足,外点法流程图,给定：x(0)R,r(0),C,1,2,k0,k=0?,入口,用无约束优化方法求罚函数的优化点,出口,+,+,-,-,算法步骤与流程图,求，得最优点,当k=0时转步骤，否则转步骤,置kk+1，并转步骤,由终止准则，若满足则转步骤，否则转,输出最优解(x*,F*)，停止计算。,算法步骤,在n维空间任取初始点x（0）,选取初始罚因子r(0),递增系数C，并置k0,用外点罚函数法解等式约束优化问题,设有二维约束优化问题,D：,h1(x)=x1+x2-10=0,如右图，h1（x）为该约束问题的可行域，这条直线以外的整个x1ox2平面为非可行域。目标函数等值线与该直线的切点为最优点,最优点,按外点法的基本思想，构造惩罚函数,xD,xD,在可行域上，惩罚项的值为零，惩罚函数值与原目标函数值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于原目标函数，即在可行域外惩罚项起到了惩罚作用。,在k的过程中，点列将趋近于原问题的最优点,对于m(k)，随着k的增大，得无约束最优点列,推广到具有一般的等式约束优化问题,D：,首先构造如下形式的外点惩罚函数,惩罚因子m（k）规定取正，m(0)0,在可行域上值为零，非可行域上，值恒大于零,混合法,用罚函数法解决有等式约束和不等式约束的一般约束（GP型）优化问题的方法，把它称为混合惩罚函数法，简称混合法。,1 混合法惩罚函数的形式及特点,一般约束问题的优化模型,D：,用惩罚函数法将其转化为无约束优化问题,惩罚函数是由原目标函数及包含约束函数的惩罚项组成。由于该问题的约束条件包含不等式约束与等式约束两部分。因此，惩罚项也应由对应的两部分组成。对应等式约束部分的只有外点法一种形式，而对应不等式的约束部分有内点法或外点法两种形式。因此按照对不等式约束处理的方法不同，混合法惩罚函数也具有两种形式。,内点形式的混合法,不等式约束部分按内点法形式处理的混合法，惩罚函数形式为,是递增序列,为了统一用一个罚因子r（k），且又按内点法形式，即,0C1,上式可写为,外点形式的混合法,不等式约束部分按外点法形式处理的混合法，惩罚函数形式为,其中，罚因子r（k）恒为正，且为递增序列，即,递增系数C1,初始点可在Rn空间内任选，初始罚因子及递增系数参照外点法选取。,2 算法步骤及流程图,参照内点法与外点法。（外点法，内点法）,例题,设有二维一般约束优化问题，数学模型为,D：,目标函数等值线及约束曲线见下图。,最优点x*既要在不等式约束包括的范围内，同时又必须在等式约束 h(x)=0的直线上，试求该约束优化问题的最优解。,解：首先写出罚函数,用内点形式的混合法写出罚函数有,用外点形式的混合法写出罚函数有,将例题中的目标函数及约束条件代入内点形式混合法或外点形式混合法罚函数中即可。,惩罚函数法总结,其统一形式,式中,（内点形式）,（外点形式）,不论哪一种形式，惩罚项的函数总为正。因此，惩罚函数 的值始终大于原目标函数F(x)的值。为使惩罚函数最终能收敛到与原目标函数的同一最优解，可通过对参数r(k)，m(k)的不断调整，使其惩罚项对F(x)的惩罚作用在搜索过程中趋于减弱并最终消。为此，惩罚项必须有如下性质,从而必存在关系,