惩罚函数法

惩罚函数法（英语：penalty method）是求解有约束的最优化问题的一种算法。

惩罚函数法的要旨是将一个有约束的最优化问题转化为一系列的无约束问题；这些无约束问题由原问题及罚函数，再加上惩罚因子组成；而且，这些无约束问题的解会收敛于所求问题的解。

基本形式

假设有以下有约束问题：

${\displaystyle \min f(\mathbf {x} )}$

满足限制

${\displaystyle c_{i}(\mathbf {x} )\leq 0~\forall i\in I.}$

惩罚函数法将问题转化成如下无约束问题的序列

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\sigma _{k}~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))}$

其中

${\displaystyle g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}.}$

在上述方程，${\displaystyle g(c_{i}(\mathbf {x} ))}$称为外部罚函数，${\displaystyle \sigma _{k}}$称为惩罚因子。在每一次叠代中，我们都增大${\displaystyle \sigma _{k}}$(例如变为原来的10倍)，然后求解该无约束问题。将每一次叠代的结果将组成一个序列，此序列的极限即为原约束问题的解。

实际应用

图像压缩优化演算法，可以利用惩罚函数以决定如何最优地将颜色域压缩成单个有代表性的数值。^[1][2]

障碍惩罚函数法

障碍惩罚函数法同样是在源问题上加入一个与惩罚函数相似的函数项，构成一个解决有约束问题的替代算法。但在这种情况下，叠代将被限制于留在可行域内部，而障碍也将持续使叠代远离可行域的边界。

参见

• 障碍惩罚函数（英语：Barrier function）
• 内点惩罚函数法（英语：Interior point method）
• 增广Lagrange惩罚函数法（英语：Augmented Lagrangian method）