第四章非线性规划2-sumt方法罚函数法

第二节 SUMT 方法（罚函数法）一、SUMT 方法的原理SUMT（ sequential unconstrained minimization technique）法，序列无约束极小化方法 ,亦称为罚函数法。它是一种不等式约束最优化问题的间接解法它的基本思想是将原来的目标函数和约束函数按一定的方式构成一个新的函数，在这个新函数中，既包括目标函数，又包括全部约束函数和一个可以变化的乘子。当这个乘子按一定的方式改变时，就得到一个新函数序列，求每一个新函数的最优解都是一个无约束最优化问题，这样就把一个约束最优化问题转化为一系列无约束最优化问题进行求解。所得到的最优解序列将逐步逼近原问题的最优解。引例一： min()fXaxs.t 0gb显然 f（X）的最优点为 x*=b，对应的最小值为f（X*）=ab用 SUMT 求解函数的最优解构造函数 11(,)()kkkrfraxrgXb可变化乘子，它是一个很小的正数。0k其最优解为： *()kkrXrba此时对应的 的最小值为,k*1(,)2krxbab最优点 和最小值 均是 的函数。当 取不同值时，它们有不同的值，而当*()kX*(,)kXrkkr时， ， ，即最后收敛于约束最优点。0krrb*,fXab（ ）0minlin(,)() |()0kk ir fRg以上分析从理论上说明了无约束最优化问题 与约束优化问题n,kr之间的联系：约束非线性规划问题可以通过构造新目标函数序mi() |()0ifXRgX列，用无约束优化方法求其极小点，并逐次逼近原问题的最优点。问题：如何构造新函数？或者说新函数具有什么特点？特点：对于某一个 （即当它为某一定值时） ，当设计点在可行区中且距离边界较远时，其对应的kr新函数的函数值不是很大，而当设计点离约束边界越近，函数值越大，特别是当设计点靠近约束边界时，一个小小的接近会引起函数值的剧烈增加。因此在对新函数 进行最优搜索过程中，搜索方向不(,)kXr会向边界方向靠近，如果向边界靠近， 会通过函数值的陡增进行惩罚。这是罚函数法的由来。(,)kXr当然必须保证设计点在可行区内。（思考：如果不在可行区内会出现什么情况？）就是罚函数， 为“惩罚因子” 。(,)kXrkr由于 的上述特征，对于处在可行区中的设计点就像有一堵“围墙”一样，阻止最优搜索进入非可行区，故又称作“围墙函数” ，引入的乘子又称为 “障碍因子” 。以上是内点法的理论分析引例二：目标函数与约束函数同上 min()fXaxs.t 0gb构造新函数： 22(,)(),max(,0) kk kRfgXRb惩 罚 函 数 惩 罚 项式中： 惩罚因子，任意一个很大的正数k对于这一新函数，当设计点在可行区时，即 ()0gbx2(,)(ax(),0kkXRfXa不满足约束条件时， gb22(,)(m(),()kk kf xRb越大， 也越大，它可看作是对不满足约束条件的一种惩罚。kR,X这时，当 = ， ， ，同样可以得到一系列曲线，可用无约束优化方法求其极小点，当k12R3时，k(,)*fab（ ）验证：以上对于不满足约束条件设计点的分析分析是外点法的理论依据。两个例子对罚函数法原理进行了理论分析，罚函数法通常分为内点法、外点法以及混合法，本节主要介绍内点法、外点法的具体做法。二、SUMT 内点法一）内点法原理内点法将新目标函数定义于可行区域内，这样它的初始点以及后面产生的迭代点序列，亦必定在可行区域内。它是求解不等式约束优化设计问题中一种十分有效的方法。内点惩罚函数法就是以不同的加权参数来构造一序列无约束的新目标函数，求这一序列惩罚因数的无约束极值点： ，使它逐渐逼近原约束问题的最扰解，而且不论原约束问题的最优点在可行*()kXr域内还是在可行域边界上，其整个搜索过程都在约束区域内进行。当设计点趋向于边界时，由于不等式约束函数趋近于零，其惩罚项的函数值就陡然增加并趋近于无穷大，这好像在可行域边界上筑起了一道“围墙” ，使迭代点始终保持在可行区域内。因此，也只有当惩罚因子 趋近于零时，才能求得约束边界上的约束最优点。kr二）内点法算法从可行区域内的某一个初始点 开始，再选取适当的初始值 ，求出惩罚函数 的最优0X0r0(,)Xr点 。然后将它作为下一次求无约束极值的初始点，并把 减至 ，再求 的最优点*0()Xr 11，如此继续下去，直至 收敛于原约束问题的最优点 。1 *()kr*其具体算法如下：三）内点法算例四）内点惩罚函数法使用中的几个问题(1)初始点 必须是严格可行的，一般可以来用随机法来产生。而且要求它不应靠近约束边界，远0X离最优点，这样容易保证计算过程稳定可靠。(2)选取适当的惩罚因子 的初始值，对于 SUMT 方法的正常计算及其汁算效率都有一定的影响。0r在 SUMT 方法方法中，只有 r0 时，惩罚函数的极值点才是原问题的约束最优解。因此，要想在一开始就通过取较小的 值来加快收敛速度，这往往是不会成功的。即使采用最稳定的最优化方法，函数也难于收敛到极值点。相反，若选取较大的 值就会增加求无约束极值的次数。因此，为了减少迭代0次数，应取较小的 值，但为了使求极值的过程稳定些，又应将 值取大些。0r 0r通常，如果初始点是一个较保守的设计(即离约束边界较远) ，那么就应该这样来选择 值，即可使0r初始点的障碍项或惩罚项不要在惩罚函数中起支配作用。由此得到的一种选择 的方法是0用这个办法通常能得到相当合理的初始值。一般推荐 P=10，对于非凸规划问题，P=150；但当初始点接近某个或几个约束边界时，上式的 值就太小了，建议取 P=100。当目标函数和约束函数的非线性程0r度不高时，直接取 也可取得较好效果。01r总的来说， 的取值没有固定的方法，它与目标函数和约束函数的性态和设计点的位置有关，实际计算时往往需要多次试算才能取得较好的初值。(3)在序列无约束极小化的过程中，惩罚因子将是一个按简单关系递减的数，即 1krc式中，c 为下降系数， c1。如果 c 过小，会造成惩罚函数的等值线变化过快，导致无约束极小化的困难。遇到这种情况，建议把 c 值取大一点，如 Cmax=0.5-0.7。内点法是机械设计中一般愿意采用的方法。因为这种方法有一个诱人的特点就是在给定一个可行的初始方案之后，它能给出一系列逐步得到改进的可行的设计方案，因此，只要设计要求允许，我们可以选用其中任一个无约束员优解，而不一定取问题的最后的约束最优解，使设计方案储备一定的能力。三、SUMT 外点法一）外点法原理与内点法将惩罚函数定义于可行域内且求解无约束问题的探索点总是保持在可行域内的特点不同，外点法的特点是将惩罚函数定义于约束可行域之外，且求解无约束问题的探索点是从可行域外部逼近原目标函数的约束最优解的。对于目标函数 f（ X） 受约束于 gi（ X） 0 的最优化设计问题，利用外点法求解时，作为无约束新目标函数的惩罚函数，其一般表达式为 1(,)(max(),kkiiRf 其中： 惩罚项1),0mkiig构造惩罚项的指数，其取值会影响惩罚函数的性质，一般取 =2 惩罚因子，是大于零的一个序列，应满足kR1210limkkR 二）外点法算法三）外点法算例四）外点惩罚函数法使用中的几个问题1.惩罚因子的大小对罚函数的性态的影响，太小太大均不好。2.初始点的选择：可以在可行区内，也可在外，只要原目标函数的极值点不在可行区内，搜索到的极值点一般在可行区外。3.最优解和约束裕量：最优解只有在 （ ）时，才会得到可行解，通常取kkR，就认为已经达到了约束边界。这样，只能取得一个接近于可行域35max()10kuQgX的非可行设计方案。当要求严格满足不等式约束条件(如强度、刚度等性能约束) 时，为了最终取得一个可行的最优设计方案必须对那些要求严格满足的约束条件，增加约束裕量 ，这就是说，定义新的约束条件()()0uugX这样可以用新定义的约束函数构成的惩