懲罰函數法

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