外罚函数法的基本思想_罚函数法例题讲解

阅前提示：文章是中山大学-最优化理论-罚函数方法1_哔哩哔哩_bilibili的学习笔记，感兴趣可以看视频，讲的非常好。

目录

SUMT算法

1、SUMT算法描述

2、几何直观理解

收敛性

1、引理

2、收敛性证明

SUMT算法

1、SUMT算法描述

在实际计算中，\(\sigma\)的选取十分重要。如果\(\sigma\)过大，则\(P(x,\sigma)\)会变得很病态，给极小点的计算带来困难；如果\(\sigma\)过小，则\(P(x,\sigma)\)的极小点远离约束问题的最优解，计算效率很差。所以更一般的做法是选择递增序列\(\{\sigma_{k}\}\)且\(\{\sigma_{k}\}\rightarrow +\infty \)。此时求解无约束优化问题：

$$
min \;\;\; P(x,\sigma_{k})=f(x) + \sigma_{k} \bar{P}(x) \tag{8}
$$

得极小点序列\(\{x_{k}\}\)，在一定条件下，此序列会收敛于约束问题的最优点，这种求解算法称为SUMT（Sequential Unconstrained Minimization Technique，序列无约束极小化技术），其具体算法过程如下：

Step0：给定初始点\(x_{0} \in R^{n}\)，终止条件\(0 \leqslant \epsilon \leqslant 1\)。\(\sigma_{1} > 1\)，\(\gamma > 1\)，令\(k := 1\)。

Step1：以\(x_{k-1}\)为初始点求解无约束优化问题：

$$
\min_{x\in R^{n}} \;\;\; P(x,\sigma_{k})=f(x)+\sigma_{k}\bar{P}(x) \tag{9}
$$

令求解出来的极小点为\(x_{k}\)。

Step2：若\(\sigma_{k}\bar{P}(x_{k}) \leqslant \epsilon\)，停算，输出\(x^{*} \approx x_{k}\)作为近似极小点。

Step3：令\(\sigma_{k+1}:=\gamma \sigma_{k}\)，\(k:=k+1\)，转至Step1。

补充说明：在Step1中，可以用任意最优化方法求解此时的无约束优化问题的极小点\(x_{k}\)。

2、几何直观理解

记原约束优化问题的全局极小点为\(x^{*}\)，原约束优化问题的曲线图像：

运行SUMT的优化问题图像如下图所示。在加入罚函数后，除可行域外的函数曲线会往上翘。\(\sigma = \sigma_{k}\)时，函数曲线为橙色曲线，此时全局极小点为\(x_{k}\)；\(\sigma = \sigma_{k+1}\)时，函数曲线为深棕色曲线，此时全局极小点为\(x_{k+1}\)。很明显，\(x_{k+1}\)要比\(x_{k}\)更接近约束问题全局极小点\(x^{*}\)。在SUMT的迭代中，由于\(\gamma > 1\)，\(\sigma\)会不断增大，惩罚力度也越来越大，使得无约束优化问题的全局极小点不断逼近\(x^{*}\)。

收敛性

1、引理

在正式证明SUMT的收敛性之前，先给出三个引理（10）、（11）、（12）：

$$ P(x_{k+1},\sigma_{k+1}) \geqslant P(x_{k},\sigma_{k}) \tag{10} $$

$$ \bar{P}(x_{k+1})\leqslant \bar{P}(x_{k}) \tag{11} $$

$$ f(x_{k+1}) \geqslant f(x_{k}) \tag{12} $$

证明：

因为\(\sigma_{k+1} > \sigma_{k} > 0\)，所以有：

$$
\begin{align*}
P(x_{k+1},\sigma_{k+1}) &= f(x_{k+1})+\sigma_{k+1}\bar{P}(x_{k+1}) \\
&\geqslant f(x_{k+1})+\sigma_{k}\bar{P}(x_{k+1}) \\
&= P(x_{k+1},\sigma_{k}) \tag{13}
\end{align*}
$$

因为\(x_{k}\)是\(P(x,\sigma_{k})\)的全局极小点，所以对所有\(x\neq x_{k}\)，都有\(P(x,\sigma_{k}) \geqslant P(x_{k},\sigma_{k})\)。因此有：

$$
P(x_{k+1},\sigma_{k})\geqslant P(x_{x},\sigma_{k}) \tag{14}
$$

 由（13）和（14）得：

$$
P(x_{k+1},\sigma_{k+1})\geqslant P(x_{k},\sigma_{k})
$$

即（10）成立。

因为\(x_{k}\)和\(x_{k+1}\)分别是\(P(x,\sigma_{k})\)和\(P(x,\sigma_{k+1})\)的全局极小点，与上述类似有：

$$
\begin{align*}
f(x_{k+1})+\sigma_{k}\bar{P}(x_{k+1}) &\geqslant f(x_{k})+\sigma_{k}\bar{P}(x_{k}) \tag{15} \\
f(x_{k})+\sigma_{k+1}\bar{P}(x_{k}) &\geqslant f(x_{k+1}) + \sigma_{k+1}\bar{P}(x_{k+1}) \tag{16} \\
\end{align*}
$$

（15）、（16）两式相加，整理可得：

$$
(\sigma_{k+1} – \sigma_{k})[\bar{P}(x_{k})-\bar{P}(x_{k+1})]\geqslant 0 \tag{17} 
$$

因为\(\sigma_{k+1} > \sigma_{k} > 0\)，所以\((\sigma_{k+1} – \sigma_{k})>0\)。若要满足（17），必有：

$$
\bar{P}(x_{k})-\bar{P}(x_{k+1}) \geqslant 0
$$

整理可得：

$$
\bar{P}(x_{k+1}) \leqslant \bar{P}(x_{k})
$$

即（11）成立。

由（15）整理可得：

$$
f(x_{k+1})-f(x_{k}) \geqslant \sigma_{k}[\bar{P}(x_{k})-\bar{P}(x_{k+1})] \tag{18}
$$

显然有\(f(x_{k+1}) \geqslant f(x_{k})\)，即（12）成立。

2、收敛性证明

设\(\{x_{k}\}\)和\(\{\sigma_{k}\}\)是SUMT算法产生的序列，\(x^{*}\)是约束优化问题的极小点。要证明SUMT的收敛性，只需证明当\(k \rightarrow +\infty\)（也就是\(\sigma_{k}\rightarrow +\infty\) ）时，\(x_{k}=x^{*}\)。令\(\lim_{k \rightarrow + \infty} x_{k} = x^{\infty}\)。

先证明\(x^{\infty}\)位于原约束优化问题的可行域内，也就是\(\bar{P}(x^{\infty})=0\)：

\(x_{k}\)是\(P(x,\sigma_{k})\)的极小点，所以有：

$$
P(x_{k},\sigma_{k})\leqslant P(x^{*},\sigma_{k})=f(x^{*})
$$

$$
P(x_{k},\sigma_{k}) \leqslant f(x^{*}) \tag{19}
$$

因此\(P(x_{k},\sigma_{k})\)有上界。又由（10）可知，\(P(x_{k},\sigma_{k})\)单调递增，所以\(\{P(x_{k},\sigma_{k})\}\)是一个单调递增有上界的序列，故极限存在，记为\(P^{\infty}\)。

同理，有：

$$
f(x_{k}) \leqslant f(x_{k})+\sigma_{k}\bar{P}(x_{k})=P(x_{k},\sigma_{k})
$$

$$
f(x_{k}) \leqslant P(x_{k},\sigma_{k}) \tag{20}
$$

结合（12）可知，\(\{f(x_{k})\}\)也是单调递增有上界的序列，因此极限也存在，记为\(f^{\infty}\)。

于是我们有：

$$
\lim_{k \rightarrow +\infty}\sigma_{k}\bar{P}(x_{k})=\lim_{k \rightarrow + \infty}[P(x_{k},\sigma_{k})-f(x_k)]=P^{\infty}-f^{\infty} \tag{21}
$$

因为\(\lim_{k \rightarrow +\infty} \sigma_{k}=+\infty \)，且\(\lim_{k \rightarrow +\infty} \sigma_{k}\bar{P}(x_{k})=P^{\infty}-f^{\infty}\)极限存在（极限是个常数），所以必有：

$$
\lim_{k \rightarrow +\infty} \bar{P}(x_{k})=0
\\
\lim_{k \rightarrow +\infty} \bar{P}(x_{k})=\bar{P}(x^{\infty})=0
$$
所以\(x^{\infty}\)是可行点。

再证明\(x^{\infty}\)是全局极小点，也就是\(f(x^{\infty})=f(x^{*})\)：

由（19）、（20）可得：

$$
f(x^{\infty}) \leqslant P(x_{k},\sigma_{k}) \leqslant f(x^{*}) \tag{22}
$$

也就是说：

$$
f(x^{\infty}) \leqslant f(x^{*}) \tag{23}
$$

又因为\(x^{*}\)是约束问题的全局极小点，故有：

$$
f(x^{*}) \leqslant f(x^{\infty}) \tag{24}
$$

由（23）和（24）可得：

$$
f(x^{\infty})=f(x^{*}) \tag{25}
$$

综上两步证明，当\(k \rightarrow +\infty\)时，\(x_{k}\)在可行域内且\(f(x_{k})=f(x^{*})\)，即\(x_{k} = x^{*}\)。证毕。

往期内容：

外罚函数法：外罚函数法（一）：外罚函数的构造_Jouski的博客-CSDN博客

多目标粒子群算法：智能优化算法：多目标粒子群优化算法（MOPSO）_Jouski的博客-CSDN博客

创作不易，点个赞再走

今天的文章
外罚函数法的基本思想_罚函数法例题讲解分享到此就结束了，感谢您的阅读。