懲罰函式法

懲罰函式法（英語：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）