ペナルティ関数法

ペナルティ関数法（ペナルティかんすうほう、英: Penalty method）とは、制約付き最適化問題（英語版）に対する解法の一種である。

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

説明

以下の制約付き最適化問題について考える:

\min _{x}f(\mathbf {x} )

subject to

c_{i}(\mathbf {x} )\leq 0~\forall i\in I.

これを無制約最適化問題に書き換える:

\min f_{p}(\mathbf {x} ):=f(\mathbf {x} )+p~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))

ただし、

g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}

である。

上記の式において $g(c_{i}(\mathbf {x} ))$ は外点ペナルティ関数^{[注釈 2]}と呼ばれ、 $p$ はペナルティ係数^{[注釈 3]}と呼ばれる。ペナルティ係数が 0 であるとき、f_p=f である。反復が進むにつれてペナルティ係数 $p$ を増大させながら無制約最適化問題を解き続けて次の反復点を求める。ペナルティ係数を増大させながら逐次無制約最適化問題を解くことで元の問題の最適解へ収束する。

制約付き最適化問題に対するペナルティ関数法は通常二次もしくは負をとらない線形のペナルティ関数を用いる^[1]。

収束性

与えられた問題の大域的最適化集合を X* とする^[2]^(Thm.9.2.1)。目的関数 f は有界な等位集合であるとし、問題は実行可能であると仮定する。このとき:

任意のペナルティ係数 p に対してペナルティ関数問題の大域的最適化集合 X_p* は必ず存在する（集合は空でない）。
任意の ε>0 に対してあるペナルティ係数 p が存在して X* におけるε-近傍 X_p* が存在する。

特に f_p が凸関数であるときに重要な性質となり、f_p の大域的最適解を求めることができる。

続いて局所最適解に関する定理について説明する^[2]^(Thm.9.2.2)。与えられた問題に対して x* を非退化^{[注釈 4]}な局所最適解とする。このとき、ある x* の近傍 V* および p₀>0 が存在して任意の p>p₀ に対してペナルティ関数付き目的関数 f_p の臨界点（x*(p)）は V* 内に存在する。このとき、x*(p) は p→∞ において x∗ に収束する。また、目的関数値 f(x*(p)) は p に対して単調非減少である。

主な応用

画像圧縮に対する最適化アルゴリズムとしてペナルティ関数法は圧縮時における最良の代表値の色を決定する際に用いられている^[3]^[4]。またペナルティ関数法は接触（英語版）のような事象を検証する際の有限要素法の計算においても用いられる。

ペナルティ関数法の利点としてペナルティ関数は新たな制約を必要とすることなく書き換えることができるので、任意の制約付き最適化問題に対して適用することができる。欠点としてはペナルティ係数 p が増大するにつれて問題の収束性が悪くなり、数値誤差も発生しやすくなる^[2]^(Sub.9.2)。

脚注

[脚注の使い方]

注釈

^ 英: penalty function
^ 英: exterior penalty function
^ 英: penalty coefficient
^ ここでいう非退化とはある点において有効な制約式の勾配が線形独立であり、最適性の二次の十分条件を満たしていることをいう。

出典

^ Boyd, Stephen; Vandenberghe, Lieven (2004). “6.1”. Convex Optimization. Cambridge university press. p. 309. ISBN 978-0521833783
^ ^a ^b ^c Nemirovsky and Ben-Tal (2023年). “Optimization III: Convex Optimization”. 2025年2月27日閲覧。
^ Galar, M.; Jurio, A.; Lopez-Molina, C.; Paternain, D.; Sanz, J.; Bustince, H. (2013). “Aggregation functions to combine RGB color channels in stereo matching”. Optics Express 21 (1): 1247–1257. Bibcode: 2013OExpr..21.1247G. doi:10.1364/oe.21.001247. hdl:2454/21074. PMID 23389018.
^ “Researchers restore image using version containing between 1 and 10 percent of information”. Phys.org (Omicron Technology Limited). 2013年10月26日閲覧。

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.
Coello, A.C.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. Variational methods for the solution of problems of equilibrium and vibrations. Bull. Amer. Math. Soc., 49, 1–23, 1943.
Wotao, Y. Optimization Algorithms for constrained optimization. Department of Mathematics, UCLA, 2015.

説明

収束性

主な応用

脚注

注釈

出典

関連項目