ペナルティ関数法のソースを表示

'''ペナルティ関数法'''（ペナルティかんすうほう、{{Lang-en-short|Penalty method}}）とは、{{仮リンク|制約付き最適化問題|en|constrained optimization}}に対する解法の一種である。

ペナルティ関数法は制約付き最適化問題を無制約最適化問題に変換して最終的には元の問題の最適化に収束させることを目指す手法である。無制約最適化問題に変換する際に{{仮リンク|目的関数|en|objective function}}に追加される項はペナルティ関数{{Efn|{{Lang-en-short|penalty function}}}}と呼ばれ、制約の違反度合いとそれに対応する係数のペナルティパラメータの積で表される。もし制約を違反している場合、ペナルティ関数は非ゼロの値をとり、制約を違反していない場合はゼロの値をとる。

== 説明 ==
以下の制約付き最適化問題について考える:
:<math> \min_x f(\mathbf x) </math>
subject to
:<math> c_i(\mathbf x) \le 0 ~\forall  i \in I. </math>

これを無制約最適化問題に書き換える:
:<math> \min f_p (\mathbf x) := f (\mathbf x) + p ~ \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> は外点ペナルティ関数{{Efn|{{Lang-en-short|''exterior penalty function''}}}}と呼ばれ、<math>p</math> はペナルティ係数{{Efn|{{Lang-en-short|''penalty coefficient''}}}}と呼ばれる。ペナルティ係数が 0 であるとき、''f<sub>p</sub>''=''f'' である。反復が進むにつれてペナルティ係数 <math>p</math> を増大させながら無制約最適化問題を解き続けて次の反復点を求める。ペナルティ係数を増大させながら逐次無制約最適化問題を解くことで元の問題の最適解へ収束する。

制約付き最適化問題に対するペナルティ関数法は通常[[二次関数|二次]]もしくは負をとらない[[線形関数|線形]]のペナルティ関数を用いる<ref>{{Cite book |last1=Boyd |first1=Stephen |title=Convex Optimization |last2=Vandenberghe |first2=Lieven |publisher=Cambridge university press |year=2004 |isbn=978-0521833783 |page=309 |chapter=6.1}}</ref>。

== 収束性 ==
与えられた問題の大域的最適化集合を X* とする<ref name=":0">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf |accessdate=2025-02-27 }}</ref>{{Rp|at=Thm.9.2.1}}。目的関数 ''f'' は有界な[[等位集合]]であるとし、問題は実行可能であると仮定する。このとき:
* 任意のペナルティ係数 ''p'' に対してペナルティ関数問題の大域的最適化集合 X<sub>p</sub>* は必ず存在する（集合は空でない）。
* 任意の ε>0 に対してあるペナルティ係数 ''p'' が存在して X* におけるε-近傍 X<sub>p</sub>* が存在する。

特に ''f<sub>p</sub>'' が凸関数であるときに重要な性質となり、''f<sub>p</sub>'' の大域的最適解を求めることができる。

続いて局所最適解に関する定理について説明する<ref name=":0" />{{Rp|at=Thm.9.2.2}}。与えられた問題に対して x* を非退化{{Efn|ここでいう非退化とはある点において有効な制約式の勾配が[[線形独立]]であり、最適性の二次の十分条件を満たしていることをいう。}}な局所最適解とする。このとき、ある x* の近傍 V* および ''p''<sub>0</sub>>0 が存在して任意の ''p''>''p''<sub>0</sub> に対してペナルティ関数付き目的関数 ''f<sub>p</sub>'' の臨界点（x*(p)）は V* 内に存在する。このとき、x*(''p'') は ''p''→∞ において x∗ に収束する。また、目的関数値 ''f''(x*(''p'')) は ''p'' に対して単調非減少である。

== 主な応用 ==
[[画像圧縮]]に対する最適化アルゴリズムとしてペナルティ関数法は圧縮時における最良の代表値の色を決定する際に用いられている<ref>{{cite journal |last1=Galar |first1=M. |last2=Jurio |first2=A. |last3=Lopez-Molina |first3=C. |last4=Paternain |first4=D. |last5=Sanz |first5=J. |last6=Bustince |first6=H. |year=2013 |title=Aggregation functions to combine RGB color channels in stereo matching |journal=Optics Express |volume=21 |issue=1 |pages=1247–1257 |doi=10.1364/oe.21.001247 |pmid=23389018 |bibcode=2013OExpr..21.1247G |hdl-access=free |hdl=2454/21074}}</ref><ref>{{cite web |title=Researchers restore image using version containing between 1 and 10 percent of information |url=http://phys.org/news/2013-10-image-version-percent.html |access-date=2013-10-26 |publisher=Phys.org (Omicron Technology Limited)}}</ref>。またペナルティ関数法は{{仮リンク|接触力学|en|Contact mechanics|label=接触}}のような事象を検証する際の[[有限要素法]]の計算においても用いられる。

ペナルティ関数法の利点としてペナルティ関数は新たな制約を必要とすることなく書き換えることができるので、任意の制約付き最適化問題に対して適用することができる。欠点としてはペナルティ係数 ''p'' が増大するにつれて問題の収束性が悪くなり、数値誤差も発生しやすくなる<ref name=":0" />{{Rp|at=Sub.9.2}}。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}
*[[:en:Alice E. Smith|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.
*Coello, A.C.[https://www.researchgate.net/publication/222857595_Coello_AC_Theoretical_and_Numerical_Constraint-Handling_Techniques_Used_with_Evolutionary_Algorithms_A_Survey_of_the_State_of_the_Art_Comput_Methods_Appl_Mech_Engrg_19111-12_1245-1287 Theoretical and Numerical Constraint-Handling Techniques Used with Evolutionary Algorithms]: A Survey of the State of the Art. Comput. Methods Appl. Mech. Engrg. 191(11-12), 1245-1287
*Courant, R. [https://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&ndash;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.

== 関連項目 ==
*[[バリア関数]]
*[[拡張ラグランジュ関数法]]
他の非線形計画問題に対するアルゴリズム:
* [[逐次二次計画法]]
* [[逐次線形計画法]]
* {{仮リンク|逐次線形二次計画法|en|Sequential linear-quadratic programming}}
* [[内点法]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:へなるていかんすうほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]