罚函数法又称乘子法，是将约束优化问题转换为无约束最优化问题的方法之一。其基本思想就是通过在原始的目标函数中添加一个障碍函数（也可以理解成惩罚函数）来代替约束条件中的不等式约束。如果当前解不满足约束条件，就在目标项上加上一个正向的惩罚（这里考虑的都是最小化问题），强迫当前解往可行域的方向走。至于正向惩罚的力度，取决于所用的映射函数，即惩罚函数。
一、非线性规划模型
\[\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}^{(k)}) = f(\boldsymbol{x})+{r}^{(k)} \sum_{i=1}^{p} \{\min [0, g_{i}(x)]\}^{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)}\)的选择对算法的成败和计算效率有显著影响。选取过小，则无约束求解的次数增多，收敛速度慢；选取过大，则非可行域内惩罚函数比原函数大得多，在起作用约束边界处产生尖点，函数形态变坏，从而限制了某些无约束优化方法的使用，导致计算失败。
罚因子递增系数\(C\) （一般取\(C=[5,10]\)）
算法步骤
(1)在\(n\)维空间任取初始点\(x^{(0)}\) 。
(2)选取初始罚因子\(r^{(0)}\)，递增系数\(C\)，并置\(k=0\)。
(3)求解无约束优化问题\(\min\phi(x,r^{(k)})\) ，得到最优点\(x_k^*\) 。
(4)当\(k=0\)时转步骤5，否则转步骤6。
置 \(k=k+1,r^{(k+1)}=Cr^{(k)},x_{k+1}^{(0)}=x_k^*\) 。
(6)由终止准则，若满足则结束算法，输出最优解；否则转步骤5。
三、实例
例1：用外点法求等式约束问题
\[\mathrm{min} \quad \frac{1}{2}x^2_1+\frac{1}{6}x^2_2 \\ \mathrm{s.t.} \quad x_1+x_2=1
\]
【解】（外点罚函数法）① 构造罚函数
\[F(x,M_k)=\frac{1}{2}x^2_1+\frac{1}{6}x^2_2+M_k(x_1+x_2-1)^2
\]
② 求偏导
\[\frac{\partial F}{\partial x_1}=x_1+2M_k(x_1+x_2-1)=0 \tag{1}
\]
\[\frac{\partial F}{\partial x_1}=\frac{1}{3}x_2+2M_k(x_1+x_2-1)=0 \tag{2}
\]
③ 联立两个偏导式，求驻点，并得到 \(x_1\)和\(x_2\)的表达式
联立 (1)和(2)，得
\[x_2=3x_1 \tag{3}
\]
将(3)代回 (1)，得到
\[x_1+2M_k(4x_1−1)=0
\]
\[x_1=\frac{2M_k}{1+8M_k}
\]
根据 (3)，得到
\[x_2=3x_1=\frac{6M_k}{1+8M_k}
\]
\[x^*=[\frac{2}{\frac{2}{M_k}+8},\frac{6}{\frac{2}{M_k}+8} ]^\mathrm{T} \tag{4}
\]
④ 令\(M_k \to \infty\)，得到结果
\[x^*=[\frac{1}{4},\frac{3}{4}]\mathrm{T}
\]
例2：求解非线性规划。
\[\text { min } f(X)=x_1+x_2 \\
\text { s.t. }-x_1^2+x_2 \geq 0 \\
x_1 \geq 0
\]
解：构造惩罚函数
\[P(X, M)=x_1+x_2+M[\min (0,-x_1^2+x_2)]^2+M[\min (0, x_1)]^2
\]
考察其驻点, 令
\[\begin{aligned}
& \frac{\partial P}{\partial x_1}=1+2 M\left[\min \left(0,-x_1^2+x_2\right)\right]\left(-2 x_1\right)+2 M\left[\min \left(0, x_1\right)\right]=0 \\
& \frac{\partial P}{\partial x_2}=1+2 M\left[\min \left(0,-x_1^2+x_2\right)\right]=0
\end{aligned}
\]
对于可行域外的点 (满足 \(x_1-1<0, x_2<0\) ), 可解得驻点
\[\left\{\begin{array}{l}
1+2 M\left(-x_1^2+x_2\right)\left(-2 x_1\right)+2 M x_1=0 \\
1+2 M\left(-x_1^2+x_2\right)=0
\end{array}\right.
\]
\[\begin{aligned}
& \text { 解得 }\left\{\begin{array}{l}
x_1=-\frac{1}{2(M+1)} \\
x_2=\frac{1}{4(M+1)^2}-\frac{1}{2 M}
\end{array}\right. \\
& \text { 令 } M \rightarrow+\infty \text {, 则 }\left\{\begin{array}{l}
x_1 \rightarrow 0 \\
x_2 \rightarrow 0
\end{array} \text {, 而 }\left[\begin{array}{ll}
0 & 0
\end{array}\right]^{\mathrm{T}} \text { 是可行点 } \rightarrow\right. \text { 问题的最优解。 } \\
\end{aligned}
\]
例3：用惩罚函数法解如下非线性规划问题。
\[\begin{array}{l}
\min \quad f({x_1},{x_2}) = 2{x_1} + 2{x_2} + 2\\
s.t.\quad \left\{ {\begin{array}{*{20}{c}}
{ - {x_1} + x_2^2 \le 1}\\
{{x_2} \ge 5}
\end{array}} \right.
\end{array}\]
解：将问题改写为
\[\begin{array}{l}
\min \quad f({x_1},{x_2}) = 2{x_1} + 2{x_2} + 2\\
s.t.\quad \left\{ {\begin{array}{*{20}{c}}
{{g_1}(x) = - {x_1} + x_2^2 - 1 \le 0}\\
{{g_2}(x) = - {x_2} + 5 \le 0}
\end{array}} \right.
\end{array}\]
参考文献
- 惩罚函数法
- 最优化方法——乘子法和外点罚函数法