算法优化之外点法（罚函数法）

pc8888888 · 发表于 2021-7-4 09:03

外点法（罚函数法）的基本概念：

   罚函数法又称乘子法，是指将有约束最优化问题转化为求解无约束最优化问题：其中  为足够大的正数，起&#34;惩罚&#34;作用，称之为罚因子， $F(x, \sigma )$ 称为罚函数。内部罚函数法也称为障碍罚函数法。
   这种方法是在可行域内部进行搜索，约束边界起到类似围墙的作用，如果当前解远离约束边界时，则罚函数值是非常小的，否则罚函数值接近无穷大的方法。在进化计算中，研究者选择外部罚函数法的原因主要是该方法不需要提供初始可行解。其中  是优化过程中新的目标函数， $G_i$ 和 $H_j$ 分别是约束条件 $g_i(x)$ 和  的函数，  是常数，称为罚因子。
外点法（罚函数法）的适用范围：

非线性规划有约束的问题，一般用在非线性规划不等式约束的问题。
外点法（罚函数法）的数学定义：

1.考虑约束问题：

   $i=1,2,...,m$ $(0)$


其中 $f(x)、g_i(x)、h_j(x)$   是 $E^n$ 上的连续函数
2. 由目标函数和约束函数组成辅助函数，把原来的约束问题转化维极小化辅助函数的无约束问题
(1) 对于等式约束问题

可定义辅助函数

$F_1(x,\sigma)=f(x)+\sigma\sum_{j=1}^{l}{h^2_j(x)}$ $(2)$
其中参数  是很大的正数
把(1)转化为无约束的问题

$minF_1(x,\sigma)$ $(3)$
显然，（3）的最优解比使得  接近零，因为如果不这样的话，问题（3）中的 $\sigma\sum_{j=1}^{l}{h^2_j(x)}$ 项将是很大的正数，现行点必不是极小点。由此可见，求解问题（3）就能够得到问题(1)的近似解。
（2）对于不等式约束问题

   $(4)$
这与上面构造辅助函数的基本思想一致：
1）在可行点辅助函数值等于原来的目标函数值
2）在不可行点，辅助函数值等于原来的目标函数值加上一个很大的正数
定义函数：

$F(x,\sigma)=f(x)+\sigma\sum_{i=1}^{m}{[max\{0,-g_i(x)\}]^2}$ $(5)$
其中  是很大的正数

$[max\{0,-g_i(x)\}]^2$ $\begin{cases} 0, 当x为可行点时\\[2ex] -g_i(x),当x不是可行点时\\[2ex] \end{cases}$
将问题（4）转化为无约束问题：

$minF(x,\sigma)$ $(6)$
通过问题（6）求得问题(4)的近似解
（3）对于一般情形(0)，定义函数

$F(x,\sigma) = f(x)+\sigma P(x)$ $(7)$
其中  具有下列形式：

$P(x)=\sum_{i=1}^{m}{\Phi(g_i(x))}+\sum_{j=1}^{l}{\psi(h_j(x))}$
典型取法：

$\Phi=[max\{0,-g_x(x)\}]^\alpha$
通常取 $\alpha=\beta=2$
这样，把约束问题（0）转化为无约束问题：

$minF(x,\sigma)=f(x)+\sigma P(x)$ $(9)$
其中  是很大的正数，  是连续函数
求解问题(9）能够得到约束问题(0)的近似解，而且  越大，近似程度越好
（1） $\sigma P(x)$ 称为罚项
（2）  称为罚因子
（3） $F(x,\sigma)$ 称为罚函数
应用案例：

例：

$min$ $x$

$x-2\geq0$

$P(x) = [max\{0,-g(x)\}]^2=\begin{cases} 0 \space\space x\geq2\\[2ex] -g_i(x)\space\space x\prec2\\[2ex] \end{cases}$
罚函数 $F(x,\sigma)=x+\sigma P(x)$
可通过求解下列无约束问题，求得（1）的近似解：

$min\space x+\sigma P(x)$ $(2)$
用解析方法求解无约束问题：

$\frac{dF}{dx}=\begin{cases}1 \space\space x\geq2\\[2ex] 1+2\sigma(x-2)\space\space x\prec2\\[2ex] \end{cases}$
令 $\frac{dF}{dx}=0$ ,解得 $\bar{x_\sigma}=2-\frac{1}{2\sigma}$
显然，  越大， $\bar{x_\sigma}$ 越接近问题（1）得最优解，当 $\sigma\rightarrow+$ 无穷大时， $\bar{x_\sigma}\rightarrow\bar{x}=2$ 。

七彩极 · 发表于 2021-7-4 09:11

您好，看完之后我觉得罚函数法和拉格朗日乘子法很像，但拉格朗日乘子法可以一步到位求得解，罚函数只是求一个近似解。请问能不能举一个例子来说明用罚函数法比拉格朗日乘子法更好求解呢？或者如果能更详细的话，能不能讲一下一般什么情况用罚函数法而不是拉格朗日乘子法？谢谢。

unityloverz · 发表于 2021-7-4 09:19

还有，我看了别人写关于罚函数法好像都会涉及到迭代什么的，但从您这里举的例子来看，似乎没有迭代的必要。能不能举一个需要迭代的例子呢？谢谢。

fwalker · 发表于 2021-7-4 09:25

mark

TheLudGamer · 发表于 2021-7-4 09:32

请问一下p(x)是什么

TheLudGamer · 发表于 2021-7-4 09:36

p(x)和惩罚因子合在一起称为罚项

mypro334 · 发表于 2021-7-4 09:44

问题连连，标题是外点法，里面又是乱七八糟，混淆视听

Mecanim · 发表于 2021-7-4 09:46

惩罚函数法可以解决有两个及以上的约束条件的非线性规划吗，

IT圈老男孩1 · 发表于 2021-7-4 09:46

你这全抄的课本啊

rustum · 发表于 2021-7-4 09:53

麻烦问下书的名称（及作者），谢谢。

		自动登录	找回密码
密码			立即注册