外点惩罚函数法

外点惩罚函数法惩罚函数法-基本概念在机械设计问题中，大多数的优化问题都属于有约束问题，其数学模型的一般形式为：为了将式（5-1）的约束优化计算问题转化为无约束问题求解，需要引入一个新的目标函数，即式中Ф（x,r1,r2)——约束问题转换后的新目标函数；r1，r2——两个不同的加权参数；G[gu（x）]，H[hv（x）]——分别由约束函数gu（x）和hv（x）所定义的某种形式的泛函数。由于在新目标函数中包含了各类约束条件，因而再求它的极值过程中随时调整设计点使它不违反约束条件，最终找到原问题的约束最优解。定义惩罚函数法（SUMT法）又称序列无约束极小化技术。这样定名，主要是在求新目标函数的极小值时，需要不断调整加权参数r1（k）和r2（k）（k=0,1,2……），使其新目标函数Ф（x,r1（k）,r2（k）)极小点的序列x*(r1（k）,r2（k）)(k=0,1,2……)逐渐收敛到原问题的约束最优解上。因此要求满足三个极限性质并在求函数Ф（x,r1（k）,r2（k）)的极小化过程中，当设计点x不满足约束条件时，使和的函数值增大，这样就对函数Ф（x,r1（k）,r2（k）)给予“惩罚”。因此称新目标函数Ф（x,r1（k）,r2（k）)为惩罚函数或增广函数，而和称为惩罚项。分类：惩罚函数法的基本思想就是把等式和不等式约束条件，经过适当定义的复合函数加到原目标函数上，从而取消了约束，转化为求解一系列的无约束问题。按照惩罚函数在优化过程中迭代点是否为内点，又分为内点法、外点法和混合法三种。区别:内点法将惩罚函数定义于可行域内且求解无约束优化问题的搜索点总是保持在可行域内，一般只用于不等式约束情况；外点法即可用于求解不等式约束优化问题，又可用于求解等式约束优化问题，主要特点是惩罚函数定义在可行域外部，从而在求解系列无约束优化问题中，从可行域外部逐渐逼近原约束优化问题的最优解。外点惩罚函数法-基本原理内点法是将可行函数定义在可行域内，而外点法与内点法不同，是将惩罚项函数定义于可行区域外部。现在用一个简单的例子来说明外点惩罚函数法的基本思想。求minf(x)=xx∈Rs.t.g(x)=1-x≤0的约束优化问题，其约束最优解显然是x*=1，f（x*）=1其约束函数取对于任意给定的惩罚因子r（k）＞0，函数Ф（x，r（k））是凸的。令函数Ф（x，r（k））的一阶导数为零，可得其无约束极值点x*（r（k））=1-1/(4r(k))和惩罚函数值为下表列出了当惩罚因子赋予不同值时的条件最优解。由此可见，当惩罚因子递增时，其极值点x*（r（k))离约束最优点x*越来越近。当r（k）→∞时，x*（r（k))→x*=1，趋于真正的约束最优点。因此，无约束极值点x*（r（k))将沿直线Ф（x*，r（k））=1/2+x*/2从约束区域外向最优点x*收敛。可见，外点惩罚函数法是通过一系列惩罚因子{r（k）（k=0,1,2……）}的函数Ф（x，r（k））的无约束极值从可行域外逐步逼近原约束问题最优解的一种方法。值得注意的是，尽管增加直至趋于无穷大，但最终的近似最优点x*仍在可行域的外部。即外点法构造的罚函数是使迭代点从可行域的外部逐渐逼近约束最优点，这正是外点法名称的由来。一般形式：外点惩罚函数的一般形式为，对于受约束于gu（x）≤0（u=1,2，……m）的优化设计问题取大括号内表示Ф（x，r（k））的无约束最小点与f（x）的约束最小点是否相等？1.x在可行域内，不管r＞0取何值，惩罚项总为零，因此惩罚函数Ф（x，r（k））的极小点x*（r（k））如果在可行域内，则该点必为原问题的最优解x*。2.当惩罚函数Ф（x，r（k））的无约束极小点x*（r（k））在可行域外，此时有这说明x*（r（k））不可能是原问题的约束最优解。从图5-7可以看出，当取r（0）值时，其极小点为x*（r（0）），此点是非可行点。很明显它不是原问题的约束最优点，当r（k）取值增大时，极小点x*（r（k））逐渐向可行域边界逼近，当r（k）值达到足够大时，x*（r（k））就是原问题最优点x*的近似解。因为当r（k）趋近于无穷大时外点惩罚函数Ф（x，r（k））的极小点x*（r（k））是在可行域外以参数r（k）为函数，将从可行域外侧逐渐向约束边界运动，最后趋近于原问题的约束最优解x*。r(k)与r（0）的选择r（k）在外点法中，惩罚因子r（k）通常是按下面递推公式增加的，即r（k）=αr（k-1）；其中α为递增系数一般取5~10。r（0）的选择：r（0）过大，惩罚函数比原目标函数大得多，使函数性态遭到破坏，从而惩罚函数的等值线变形或偏心，求极值困难；r（0）过小，会使迭代次数增加。建议终止准则可用下述两者之一⑴相邻两次惩罚函数无约束最优点之间的距离已足够的小。设ε1为收敛精度，一般取ε1=10-4-10-5，则需要满足⑵相邻两次惩罚函数值的相对变化量已足够小。设ε2为收敛精度，一般取ε2=10-3-10-4，则需要满足外点法算法步骤外点法流程图给定：x(0)∈R,r(0),α,ε1,ε2k=0k=0?入口用无约束优化方法求罚函数的优化点*kx)(*kxFF(1)()0(0)*11kkkkrrFFxxkk)(*,***kkxFFxx出口YYNN㈣算法步骤与流程图200FFF使用中的问题外点惩罚函数法的初始点x（0），可以任意选择，因为不论初始点选在可行域内或外，只要f（x）的无约束极值点不在可行域内，其函数Ф（x，r（k））的极值点均在约束可行域外。这样，当惩罚因子的增大倍数不太大时，用前一次求得的无约束极值点x*r（k-1），作为下次求minФ（x，r（k））的初始点x（0），对于加快搜索速度是有好处的，特别是对于采用具有较高收敛速度的无约束最优化方法，若初始点离极值点越近，则其收敛速度越快。在外点法中，判断无约束极值点x*r（k）是否为最优点x*，其中，要看x*r（k）点离约束面的距离，若x*r（k）点处于约束边界上，则gu（x*r（k））=0，但实际上只有当迭代次数k→∞才能达到，这需要大量计算。因此，通常规定某一精度值δ0=10-3~10-5,只要x*r（k）满足Q=max{gu[x*(r(k))]u=1,2,……m}≤δ0条件，就认为已经达到约束边界。这样只能取得一个接近于可行域的非可行设计方案。当要求严格满足不等式的约束条件时，为了最终取得一个可行的最优化设计方案，必须对那些要求严格满足的约束条件，增加约束欲量——δ，定义新的约束条件g'u(x)=gu(x)+δ≤0u=1,2,……m用外点罚函数法解等式约束优化问题设有二维约束优化问题h1(x)=x1+x2-10=0如右图，h1(x)为该约束问题的可行域，这条直线以外的整个x1ox2平面为非可行域。目标函数等值线与该直线的切点为最优点最优点S.T.:按外点法的基本思想，构造惩罚函数x∈Dx∉D在可行域上，惩罚项的值为零，惩罚函数值与原目标函数值相同；在非可行域上，惩罚函数的值恒为正，罚函数大于原目标函数，即在可行域外惩罚项起到了惩罚作用。在k→∞的过程中，点列将趋近于原问题的最优点对于r(k)，随着k的增大，得无约束最优点列