惩罚函数法

数学优化

发布日期: 2022-06-18

更新日期: 2022-08-16

文章字数: 2.2k

阅读时长: 9 分

基本思想：通过构造惩罚函数将约束问题转化为无约束问题，进而用无约束最优化方法求解。主要分为内点法和外点法。
注意：罚函数法对目标函数的凹凸性没有要求，且结合启发式算法（如遗传算法、蚁群算法、禁忌搜索等）几乎可以求解任何问题。因为启发式算法无需目标函数的梯度等信息。

一、惩罚函数

约束优化问题
$$
\begin{array}{ll}
\min & f(\boldsymbol{x}) \
\text { s. t. } & g_{i}(\boldsymbol{x}) \geqslant 0, \quad i=1, \cdots, p \
& h_{j}(\boldsymbol{x})=0, \quad j=1, \cdots, q
\end{array}
$$
其中，$f(\boldsymbol{x}),g_i(\boldsymbol{x})(i=1,2,\cdots,p)$ 和 $h_j(\boldsymbol{x})(j=1,2,\cdots,q)$ 是 $\mathbb{R}^n$ 上的连续函数。

由于约束条件是非线性的，不能用消元法将其转换为无约束问题，在求解时需同时考虑目标函数值下降和满足约束条件。可以通过由目标函数和约束条件组成惩罚函数，将原问题转化为极小化惩罚函数的无约束问题。

惩罚函数

对于一般情形（多个等式/不等式约束条件），惩罚函数的一般形式为：
$$
\phi(\boldsymbol{x},{r},\boldsymbol{m})=f(\boldsymbol{x})+{r} \sum_{i=1}^{p} G\left[g_{i}(x)\right]+{m} \sum_{j=1}^{q} H\left[h_{j}(x)\right]
$$
其中，${r},{m}$ 称为罚因子，${r}G\left[g_{i}(x)\right],{m}
H\left[h_{j}(x)\right]$ 称为惩罚项。且其典型构造方法为：
$$
\left{\begin{array}{l}
G\left[g_{i}(x)\right]= \begin{cases}\frac{1}{g_{i}(x)};\text{or};-\ln\left(g_{i}(x)\right)&\text{(内点形式)} \
\left{\min \left[0, g_{i}(x)\right]\right}^{2}&(\text{外点形式})\end{cases} \
H\left[h_{j}(x)\right]=\left[h_{j}(x)\right]^{2}
\end{array}\right.
$$
若要使用内点形式，且统一使用一个罚因子序列，则可以使 ${m}^{(k)}=\frac{1}{\sqrt{r^{(k)}}}$ （对于外点法，罚因子是递增序列，对于内点法，罚因子是递减序列）。

基本原理

当 $\boldsymbol{x}$ 为可行点时，惩罚项等于0，即 $\phi(\boldsymbol{x},{r},{m})=f(\boldsymbol{x})$ ；
当 $\boldsymbol{x}$ 为不可行点，惩罚项是一个很大的正数，其存在是对点脱离可行域的惩罚，作用是在极小化过程中迫使迭代点靠近可行域。

因为惩罚函数一定满足 $\phi(\boldsymbol{x},{r},{m})\ge f(\boldsymbol{x})$ ，随着迭代的进行，惩罚函数应该逐渐逼近原函数，即惩罚项逐渐趋于0，只有让迭代点靠近可行域，才能达到这个目的。

二、内点法

内点法总是从内点出发，并保持在可行域内进行搜索，仅适用于只包含不等式约束的优化问题。

优化问题
$$
\begin{array}{ll}
\min & f(\boldsymbol{x}) \
\text { s. t. } & g_{i}(\boldsymbol{x}) \geqslant 0, \quad i=1, \cdots, p
\end{array}
$$
其中，$f(\boldsymbol{x}),g_i(\boldsymbol{x})(i=1,2,\cdots,p)$ 是 $\mathbb{R}^n$ 上的连续函数。可行域可记为
$$
S={\boldsymbol{x}|g_i(\boldsymbol{x})\ge 0,;i=1,2,\cdots,p}
$$
惩罚函数
$$
\phi(\boldsymbol{x},{r})=f(\boldsymbol{x})+{r}\sum_{i=1}^pG(\boldsymbol{x})
$$
其中，当点 $\boldsymbol{x}$ 靠近可行域边界时， $G(\boldsymbol{x})\rightarrow\infty$ 。$G(\boldsymbol{x})$ 的两种最重要的形式为：
$$
G(\boldsymbol{x})=\frac{1}{g_i(\boldsymbol{x})};\text{or};-\ln(g_i(\boldsymbol{x}))
$$
$r$ 是很小的正数。这样，当点 $\boldsymbol{x}$ 靠近可行域边界时，$\phi(\boldsymbol{x},{r})\rightarrow\infty$ ；反之，由于 $r$ 的存在，惩罚函数的取值近似等于原函数。这样可以将迭代点限制在可行域内。因此，可通过求解无约束的极小化惩罚函数问题作为原问题的近似解：
$$
\begin{array}{ll}
\min & \phi(\boldsymbol{x},{r}) \
\text { s. t. } &\boldsymbol{x}\in \text{int};S
\end{array}
$$
罚因子的变化趋势

罚因子是一个逐渐变小的值，可表示为：
$$
r^{(k)}=Cr^{(k-1)}
$$
$C$ 是罚因子递减系数，通常取 $0<C<1$ ，即 $\lim_\limits{k\rightarrow\infty}r^{(k)}=0$ 。因此随着迭代进行，惩罚函数会逐渐变小，进而逼近原函数。

参数选择

初始点 $x^{(0)}$
1. 自定法。根据经验决定。
2. 搜索法。任选初始点，通过对初始点约束函数值的检验，按其对每个约束的不满足程度加以调节，将 $x^{(k)}$ 逐步引入到可行域内，成为可行初始点。
初始罚因子 $r^{(0)}$
1. 若 $r^{(0)}$ 太大，则一开始惩罚函数将远大于原目标函数值，迭代点也将远离原问题最优点，需要经过较长时间搜索才能逐渐逼近；
2. 若 $r^{(0)}$ 太小，则一开始惩罚项的作用很小，可行域内惩罚函数与原目标函数接近，在可行域边界附近惩罚函数值才突然提高，这样回导致惩罚函数边界附近出现深沟谷地，罚函数形态变得恶劣，从而限制了某些无约束优化方法的使用，导致计算失败。
罚因子递减系数 $C$ （一般取 $C=[0.1,0.5]$）
1. 一般认为其选择对算法的成败影响不大；
2. 若 $C$ 较小，则罚因子下降快，可减少无约束问题的优化次数，但因前后两次无约束最优点的距离较远，可能会使后一次无约束优化本身的迭代次数增多，且迭代最优点间隔大，对约束最优点的逼近不利；
3. 若 $C$ 较大，则无约束优化次数增多。

终止条件

相邻两次惩罚函数无约束最优点间距离足够小。一般取收敛精度 $\varepsilon_1=[10^{-4},10^{-5}]$，满足
$$
|x^*k-x^*{k-1}|\le\varepsilon_1
$$
相邻两次惩罚函数值相对变化量足够小。一般取 $\varepsilon_2=[10^{-3},10^{-4}]$ ，满足
$$
\left|\frac{\phi_{k}^{}-\phi_{k-1}^{}}{\phi_{k}^{*}}\right| \leq \varepsilon_{2}
$$

算法步骤

构造内点惩罚函数 $\phi(x,r^{(k)})=f(x)+r^{(k)}\sum_\limits{i=1}^p\frac{1}{g_i(x)}$ 。
选择可行初始点 $x^{(0)}$ ，初始罚因子 $r^{(0)}$ ，罚因子递减系数 $C$ ，收敛精度 $\varepsilon_1,\varepsilon_2$，置 $k=0$ 。
求解无约束优化问题 $\min\phi(x,r^{(k)})$ ，得到最优点 $x_k^*$。
当 $k=0$ 时转步骤5，否则转步骤6。
置 $k=k+1,r^{(k)}=Cr^{(k-1)},x_{k+1}^{(0)}=x_k^*$ 。
由终止准则，若满足则结束算法，输出最优解；否则转步骤5。

三、外点法

外点法不保证搜索点保持在可行域内（搜索范围包括可行域和不可行域），适用于包含不等式约束或等式约束的优化问题。

优化问题

仅以不等式约束为例（等式约束类似，二者混合形式的可见第一节惩罚函数统一形式部分）

$$
\begin{array}{ll}
\min & f(\boldsymbol{x}) \
\text { s. t. } & g_{i}(\boldsymbol{x}) \geqslant 0, \quad i=1, \cdots, p
\end{array}
$$

惩罚函数
$$
\phi(\boldsymbol{x},{r}^{(k)})=f(\boldsymbol{x})+{r}^{(k)} \sum_{i=1}^{p}\left{\min \left[0, g_{i}(x)\right]\right}^{2}
$$
其中，$\boldsymbol{r}^{(k)}$ 为趋于无穷大的严格递增正数列，$r^{(k)}=Cr^{(k-1)}$ 且 $C>1$ ，$\lim_\limits{k\rightarrow\infty}r^{(k)}=\infty$ 。迭代点在可行域内时，惩罚项为0，惩罚函数等于原函数；迭代点在可行域外时，惩罚项大于0，大于原函数。因此，由于罚因子严格递增，随着迭代进行，可以迫使惩罚项趋于0，从而逼近原函数。

几何解释

参数选择

初始点 $x^{(0)}$

可行域及非可行域内均可。
初始罚因子 $r^{(0)}$
$r^{(0)}$ 的选择对算法的成败和计算效率有显著影响。
1. 选取过小，则无约束求解的次数增多，收敛速度慢；
2. 选取过大，则非可行域内惩罚函数比原函数大得多，在起作用约束边界处产生尖点，函数形态变坏，从而限制了某些无约束优化方法的使用，导致计算失败。（比如利用梯度下降法，由于其搜索过程是锯齿形的，边界处的尖点可能会导致搜索点反复横跳？并且由于前后迭代值差距不大而达到精度终止算法，实际却没有取到最优点——个人想法，有待实验）
罚因子递增系数 $C$ （一般取 $C=[5,10]$）