ペナルティ関数法

ペナルティ関数法（ペナルティかんすうほう、）とは、に対する解法の一種である。

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

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

subject to

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

ただし、 である。

上記の式において は外点ペナルティ関数と呼ばれ、 はペナルティ係数と呼ばれる。ペナルティ係数が 0 であるとき、fp=f である。反復が進むにつれてペナルティ係数 を増大させながら無制約最適化問題を解き続けて次の反復点を求める。ペナルティ係数を増大させながら逐次無制約最適化問題を解くことで元の問題の最適解へ収束する。

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

収束性 与えられた問題の大域的最適化集合を X* とする。目的関数 f は有界な等位集合であるとし、問題は実行可能であると仮定する。このとき: 任意のペナルティ係数 p に対してペナルティ関数問題の大域的最適化集合 Xp* は必ず存在する（集合は空でない）。 任意の ε>0 に対してあるペナルティ係数 p が存在して X* におけるε-近傍 Xp* が存在する。

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

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

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

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

脚注

注釈

出典

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.

関連項目 バリア関数 拡張ラグランジュ関数法 他の非線形計画問題に対するアルゴリズム: 逐次二次計画法 逐次線形計画法 逐次線形二次計画法 内点法