罚函数方法（转载） ペナルティ

罚函数方法是求解约束（极小）优化问题的一类较好的算法。其基本思想：根据约束的特点构造某种惩罚函数，并把惩罚函数添加到目标函数上去，从而得到一个增广目标函数，使约束优化问题的求解转化为一系列无约束极小优化问题的求解。故称此类算法为系列无约束极小化方法（Sequential Unconstrained Minimization Technique, SUMT）。常用的有SUMT外点法和SUMT内点法。

SUMT外点法：对违反约束条件的点在目标函数中加入响应的惩罚（！），而对可行点不予惩罚，其迭代点一般在可行域外部移动（？）。随着迭代的进行，惩罚也逐次加大，以迫使迭代点不断的逼近并最终称为可行点，以便找到原约束优化问题的最优解。

SUMT外点法数学描述：在任一点x，等式约束的违反程度可用|hj(x)|来度量，不等式约束gi(x)>=0的违反程度可用|min(0,gi(x))|来度量。

惩罚项：p(x)=sumi=1,m(|min(0,gi(x))|a ) + sumj=1,l(|hj(x)|b ). 取a＝b＝2.则NPL问题的罚函数，即增广目标函数为：T（x，c）＝f（x）＋cp（x）。c称为罚因子，c>0。当c足够大（？）的时候增广函数的最优解是原约束优化问题的最优解。

SUMT内点法：从一初始可行点开始迭代，设法是迭代过程始终保持在可行域内进行，为此，在可行域边界设置一道墙（？）对企图穿越这道墙的点在目标函数中加入响应的阻碍（？），越接近边界，障碍就越大，从而保证迭代点始终在可行域内部进行迭代。

内点法仅用于含有不等式约束的非线性规划问题。

增广目标函数：F(x,r)=f(x)+rB(x).

障碍函数常用形式：

对数型：B(x)=-sumi=1,m(ln(gi(x))).

倒数型：B(x)=sumi=1,m(1/gi(x)).

当r趋于0时，增广函数的无约束问题的最优解可望趋于NIP问题的最优解。

混合罚函数：

P(x,r) = f(x) + r B(x) + p(x)/r;其中r趋于0正为罚参数。

例如：P(x,r) = f(x) - r sumi=1,m(ln(gi(x))) + {sumi=1,m(|min{0,gi(x)}| a + sumj=1,l(|hj(x)| b))}/r ;

精确罚函数：为了克服罚函数法需要求解一系列无约束优化问题的缺点，人们试图通过求解单个无约束优化问题来获得原约束优化问题的最优解，即，只要罚参数取适当的有限值（称阀值）后，该罚函数的无约束优化问题的最小点就是原约束优化问题的最优解，这样得到的罚函数通常称为精确罚函数。




Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=423922

http://blog.csdn.net/yuwenhui1981/archive/2005/07/13/423922.aspx