查看“︁懲罰函數法”︁的源代码

{{noteTA|G1=Math|1=zh-hans:迭代;zh-hant:疊代;|G2=IT}}
'''懲罰函數法'''（{{lang-en|'''penalty method'''}}）是求解有約束的[[最優化]]問題的一種[[算法]]。

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

== 基本形式 ==
假設有以下有約束問題：
:<math> \min f(\mathbf x) </math>
滿足限制
:<math> c_i(\mathbf x) \le 0 ~\forall  i \in I. </math>
懲罰函數法將問題轉化成如下無約束問題的序列
:<math> \min \Phi_k (\mathbf x) = f (\mathbf x) + \sigma_k ~ \sum_{i\in I} ~ g(c_i(\mathbf x)) </math>
其中
:<math> g(c_i(\mathbf x))=\max(0,c_i(\mathbf x ))^2. </math>
在上述方程，<math> g(c_i(\mathbf x))</math>稱為外部罰函數，<math>\sigma_k</math>稱為懲罰因子。在每一次疊代中，我們都增大<math>\sigma_k</math>(例如變為原來的10倍)，然後求解該無約束問題。將每一次疊代的結果將組成一個序列，此序列的極限即為原約束問題的解。

== 實際應用 ==
圖像壓縮優化演算法，可以利用懲罰函數以決定如何最優地將顏色域壓縮成單個有代表性的數值。<ref>{{cite journal|title=Aggregation functions to combine RGB color channels in stereo matching|last=Galar|first=M.|last2=Jurio|first2=A.|journal=Optics Express|doi=10.1364/oe.21.001247|year=2013|volume=21|pages=1247–1257|last3=Lopez-Molina|first3=C.|last4=Paternain|first4=D.|last5=Sanz|first5=J.|last6=Bustince|first6=H.}}</ref><ref>{{cite web|url=http://phys.org/news/2013-10-image-version-percent.html|title=Researchers restore image using version containing between 1 and 10 percent of information|accessdate=2013-10-26|publisher=Phys.org (Omicron Technology Limited)|archive-date=2020-12-02|archive-url=https://web.archive.org/web/20201202153916/https://phys.org/news/2013-10-image-version-percent.html|dead-url=no}}</ref>

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

== 參見 ==
* {{Link-en|障碍懲罰函數|Barrier function}}
* {{Link-en|內點懲罰函數法|Interior point method}}
* {{Link-en|增廣Lagrange懲罰函數法|Augmented Lagrangian method}}

== 參考文獻 ==
{{reflist|30em}}
{{reflist|list=
* Smith, Alice E.; Coit David W. [http://140.138.143.31/teachers/ycliang/heuristic%20optimization%20912/penalty%20function.pdf Penalty functions] Handbook of Evolutionary Computation, Section C 5.2. Oxford University Press and Institute of Physics Publishing, 1996.

* Courant, R. [http://www.ams.org/bull/1943-49-01/S0002-9904-1943-07818-4/S0002-9904-1943-07818-4.pdf Variational methods for the solution of problems of equilibrium and vibrations]. Bull. Amer. Math. Soc., 49, 1&#x2013;23, 1943.

* Wotao, Y. [https://web.archive.org/web/20170306141802/http://www.math.ucla.edu/~wotaoyin/math164/slides/wotao_yin_optimization_lec13_algorithms_for_constrained_optimization.pdf Optimization Algorithms for constrained optimization]. Department of Mathematics, UCLA, 2015.
}}

[[Category:數學最佳化]]
[[Category:運籌學]]