KNOWECON WIKI

ARTICLE

罚函数

罚函数 (Penalty Function) 罚函数 (Penalty Function) 是最优化理论中将约束优化问题转化为无约束优化问题的一类经典方法。其核心思想是：在原目标函数上添加一个惩罚项，当迭代点违反约束条件时惩罚项急剧增大，迫使搜索路径从可行域外部（或内部）逼近最优解。罚函数法是求解非线性规划问题的基石之一，也是现代内点法 (Interior

浏览 9 更新 2025-11-08

罚函数 (Penalty Function)

罚函数 (Penalty Function) 是最优化理论中将约束优化问题转化为无约束优化问题的一类经典方法。其核心思想是：在原目标函数上添加一个惩罚项，当迭代点违反约束条件时惩罚项急剧增大，迫使搜索路径从可行域外部（或内部）逼近最优解。罚函数法是求解非线性规划问题的基石之一，也是现代内点法 (Interior Point Method) 的理论先驱。

基本原理

考虑一般约束优化问题：

min⁡f(x)s.t.gi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\begin{aligned} \min \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}

罚函数法构造增广目标函数 (Augmented Objective)：

P(x,μ)=f(x)+μ⋅ψ(x)P(\mathbf{x}, \mu) = f(\mathbf{x}) + \mu \cdot \psi(\mathbf{x})

其中 μ>0\mu > 0 为罚参数，ψ(x)\psi(\mathbf{x}) 为惩罚项，度量约束违反程度。通过求解罚参数不断加重的子问题序列（μk→∞\mu_k \to \infty 或内点情形下 μk→0\mu_k \to 0），迭代点列被驱赶向原问题的最优解。

外点罚函数法 (Exterior Penalty Method)

外点法允许迭代点位于可行域之外，从不可行侧靠近边界。惩罚项典型构造为二次形式：

ψ(x)=∑i=1m[max⁡(0,gi(x))]2+∑j=1p[hj(x)]2\psi(\mathbf{x}) = \sum_{i=1}^{m} [\max(0, g_i(\mathbf{x}))]^2 + \sum_{j=1}^{p} [h_j(\mathbf{x})]^2

算法框架： 选取 μ0>0\mu_0 > 0，初始点 x0\mathbf{x}_0（可不可行），放大系数 c>1c > 1；求解无约束子问题 min⁡P(x,μk)\min P(\mathbf{x}, \mu_k)；若 μkψ(xk)<ε\mu_k \psi(\mathbf{x}_k) < \varepsilon 则停止，否则令 μk+1=cμk\mu_{k+1} = c\mu_k 继续迭代。

优点： 对初始点无可行性要求，编程简单。缺点： 罚参数趋于无穷时 Hessian 矩阵病态 (Ill-conditioned)，子问题求解困难；中间迭代点不可行。

内点罚函数法 / 障碍函数法 (Barrier Method)

内点法强制迭代点保持在可行域内部，在边界建立趋于无穷的障碍。常用对数障碍函数：

B(x,μ)=f(x)−μ∑i=1mln⁡(−gi(x))B(\mathbf{x}, \mu) = f(\mathbf{x}) - \mu \sum_{i=1}^{m} \ln(-g_i(\mathbf{x}))

当 x\mathbf{x} 趋于边界时，−ln⁡(−gi)→+∞-\ln(-g_i) \to +\infty。随 μ→0\mu \to 0，序列沿中心路径 (Central Path) 收敛至边界上的最优解，催生了现代原对偶内点法 (Primal-Dual Interior Point Method)。

精确罚函数 (Exact Penalty Function)

精确罚函数存在有限阈值，超过该阈值后单次无约束极小化即得原问题最优解。经典 ℓ1\ell_1 形式：

P1(x,ρ)=f(x)+ρ(∑i=1mmax⁡(0,gi(x))+∑j=1p∣hj(x)∣)P_1(\mathbf{x}, \rho) = f(\mathbf{x}) + \rho \left( \sum_{i=1}^{m} \max(0, g_i(\mathbf{x})) + \sum_{j=1}^{p} |h_j(\mathbf{x})| \right)

当 ρ\rho 大于所有活跃约束对应的最优拉格朗日乘子的 ∞\infty-范数时，P1P_1 的局部极小点恰为原问题的局部极小点，但代价是在约束边界处不可微。

应用

罚函数思想已渗透到现代计算科学中：

  • 机器学习：岭回归的 ℓ2\ell_2 正则项是对系数的二次惩罚；LASSO 的 ℓ1\ell_1 正则产生稀疏解；支持向量机的惩罚系数 CC 对误分类施以铰链损失。
  • 深度学习：权重衰减、Dropout 等正则化可从罚函数视角理解。
  • 贝叶斯推断：先验分布可视为对似然的惩罚项——拉普拉斯先验对应 ℓ1\ell_1，高斯先验对应 ℓ2\ell_2。
  • 最优控制：MPC 中的约束处理常采用罚函数思想。

注意事项

罚参数初值和放大系数的选择需平衡：μ0\mu_0 过大或 cc 过大导致首个子问题即病态；μ0\mu_0 过小或 cc 过小则外层迭代过多。外点法的中间迭代点不可行，若应用要求每次迭代均可行的方案应优先考虑内点法。对非凸约束问题，罚函数法可能收敛到不可行域中的局部极小点或鞍点，需结合多重初始点策略。