ペナルティ方式

ペナルティ法は、制約付き最適化問題を解決するための特定のクラスのアルゴリズムです。

ペナルティ法は、制約付き最適化問題を、解が理想的には元の制約付き問題の解に収束する一連の制約なし問題に置き換えます。制約なし問題は、ペナルティ パラメータに制約違反の尺度を乗じた目的関数に、ペナルティ関数と呼ばれる項を追加することによって形成されます。制約違反がある場合、違反の尺度はゼロ以外になり、制約違反がない領域ではゼロになります。

次のような制約付き問題を解決しているとします。

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

対象となる

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

この問題は、一連の制約なし最小化問題として解くことができる。

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

どこ

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

上記の式では、は外部ペナルティ関数で、はペナルティ係数です。ペナルティ係数が 0 のとき、f _p = fです。この方法の各反復では、ペナルティ係数を（たとえば 10 倍に）増加させ、制約のない問題を解き、その解を次の反復の初期推定値として使用します。連続する制約のない問題の解は、元の制約のある問題の解に漸近的に収束します。 ${\displaystyle g(c_{i}(\mathbf {x} ))}$${\displaystyle p}$${\displaystyle p}$

制約付き最適化における一般的なペナルティ関数は、二次ペナルティ関数とデッドゾーン線形ペナルティ関数である。^[1]

まず、元の問題X*のグローバル最適化集合を考える。^{[2] : Thm.9.2.1}目的関数fが有界レベル集合を持ち、元の問題が実行可能であると仮定する。すると、

• すべてのペナルティ係数pについて、ペナルティ対象問題のグローバル最適化器の集合 X _p * は空ではありません。
• すべてのε>0に対して、集合X _p *が集合X*のε近傍に含まれるようなペナルティ係数pが存在する。

この定理は、 f _pが凸の場合に最も役立ちます。この場合には、 f _pのグローバル最適化子を見つけることができるためです。

2番目の定理は、局所最適化装置を考慮します。^{[2] : Thm.9.2.2} x* を元の問題の非退化局所最適化装置とします（「非退化」とは、アクティブな制約の勾配が線形独立であり、2次の十分な最適性条件が満たされていることを意味します）。すると、 x* の近傍 V* と、あるp _{0 >0 が存在し、すべての}p > p ₀に対して、ペナルティ付き目的関数f _{p は}V* 内にちょうど1つの臨界点（x*(p) で示される）を持ち、 x*( p ) はp →∞のときに x* に近づきます。また、目的関数値f (x*( p )) はpとともに弱増加します。

画像圧縮最適化アルゴリズムでは、ペナルティ関数を利用して、色の領域を単一の代表値に圧縮する最適な方法を選択できます。^{[3] [4]ペナルティ法は、計算力学、特に}有限要素法で、接触などの条件を強制するためによく使用されます。

ペナルティ法の利点は、制約のないペナルティ付き目的関数が得られれば、制約のない最適化手法を使って解くことができることです。欠点は、ペナルティ係数pが大きくなるにつれて、制約のない問題が悪条件になることです。つまり、係数が非常に大きくなり、数値エラーが発生し、制約のない最小化の収束が遅くなることがあります。^{[2] : Sub.9.2}

バリア法は、制約付き最適化のためのアルゴリズムの代替クラスを構成します。これらの方法でも、目的関数にペナルティのような項が追加されますが、この場合、反復は実行可能領域の内部にとどまるように強制され、バリアは反復が実行可能領域の境界から離れるようにバイアスをかけるために配置されます。これらは、ペナルティ法よりも実質的に効率的です。

拡張ラグランジュ法は、ペナルティ係数を無限大にすることなく高精度の解を得ることができる代替ペナルティ法です。これにより、制約のないペナルティ問題が簡単に解けるようになります。

その他の非線形計画アルゴリズム:

• 逐次二次計画法
• 逐次線形計画法
• 逐次線形二次計画法
• 内点法

スミス、アリス E. ; コイト デイビッド W. ペナルティ関数 進化計算ハンドブック、セクション C 5.2。オックスフォード大学出版局および物理学研究所出版、1996 年。

Coello, AC[1]: 進化的アルゴリズムで使用される理論的および数値的制約処理技術: 最新技術の調査。Comput. Methods Appl. Mech. Engrg. 191(11-12), 1245-1287

Courant, R. 平衡と振動の問題を解くための変分法。Bull. Amer. Math. Soc.、49、1–23、1943 年。

Wotao, Y. 制約付き最適化のための最適化アルゴリズム。UCLA 数学部、2015 年。