懲罰函數法

懲罰函數法

懲罰函數法是求解有約束的最優化問題的一種演演算法。

懲罰函數法的要旨是將一個有約束的最優化問題轉化為一系列的無約束問題;這些無約束問題由原問題及罰函數,再加上懲罰因子組成;而且,這些無約束問題的解會收斂於所求問題的解。

基本形式


假設有以下有約束問題:
滿足限制
懲罰函數法將問題轉化成如下無約束問題的序列
其中
在上述方程,稱為外部罰函數,稱為懲罰因子。在每一次迭代中,我們都增大(例如變為原來的10倍),然後求解該無約束問題。將每一次迭代的結果將組成一個序列,此序列的極限即為原約束問題的解。

實際應用


圖像壓縮優化演演算法,可以利用懲罰函數以決定如何最優地將顏色域壓縮成單個有代表性的數值。

障礙懲罰函數法


障礙懲罰函數法同樣是在源問題上加入一個與懲罰函數相似的函數項,構成一個解決有約束問題的替代演演算法。但在這種情況下,迭代將被限制於留在可行域內部,而障礙也將持續使迭代遠離可行域的邊界。

參見


• 障礙懲罰函數
• 內點懲罰函數法
• 增廣Lagrange懲罰函數法