懲罰函數法(英語:penalty method)是求解有約束的最佳化問題的一種演算法

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

基本形式

編輯

假設有以下有約束問題:

 

滿足限制

 

懲罰函數法將問題轉化成如下無約束問題的序列

 

其中

 

在上述方程, 稱為外部罰函數, 稱為懲罰因子。在每一次疊代中,我們都增大 (例如變為原來的10倍),然後求解該無約束問題。將每一次疊代的結果將組成一個序列,此序列的極限即為原約束問題的解。

實際應用

編輯

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

障礙懲罰函數法

編輯

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

參見

編輯

參考文獻

編輯
  1. ^ Galar, M.; Jurio, A.; Lopez-Molina, C.; Paternain, D.; Sanz, J.; Bustince, H. Aggregation functions to combine RGB color channels in stereo matching. Optics Express. 2013, 21: 1247–1257. doi:10.1364/oe.21.001247. 
  2. ^ Researchers restore image using version containing between 1 and 10 percent of information. Phys.org (Omicron Technology Limited). [2013-10-26]. (原始內容存檔於2020-12-02). 
  • Smith, Alice E.; Coit David W. Penalty functions Handbook of Evolutionary Computation, Section C 5.2. Oxford University Press and Institute of Physics Publishing, 1996.