バリア機能

数学の分野である制約付き最適化において、バリア関数は、最適化問題の実行可能領域の境界に近づくにつれて値が無限大に増加する連続関数である。 ^{[1] [2]このような関数は、不等式}制約を、扱いやすい目的関数のペナルティ項に置き換えるために使用される。バリア関数は、解が実行可能領域の内部にとどまるように強制するペナルティ関数であるため、内部ペナルティ関数とも呼ばれる。

最も一般的な 2 つのバリア関数は、逆バリア関数と対数バリア関数です。対数バリア関数への関心が再び高まったのは、主双対内点法との関連がきっかけでした。

次の制約付き最適化問題を考えてみましょう。

f ( x )を最小化する

x ≤ bを条件とする

ここでbは定数である。不等式制約を取り除いた場合、問題は次のように書き換えられる。

f ( x ) + c ( x )を最小化する、

ここで、x > bの場合はc ( x ) = ∞、それ以外の場合は 0 です。

この問題は最初の問題と同等です。不等式は解消されますが、ペナルティ関数c、つまり目的関数f ( x ) + c ( x )が不連続になるという問題が生じ、微積分を使用して解くことができなくなります。

バリア関数は、gからcへの連続近似値であり、 x が上からbに近づくにつれて無限大に近づきます。このような関数を使用して、新しい最適化問題が定式化されます。

f ( x ) + μ g ( x )を最小化する 

ここで、μ > 0は自由パラメータである。この問題は元の問題と同等ではないが、μがゼロに近づくにつれて、より良い近似値となる。^[3]

対数バリア関数の場合、のときは がとして定義され、以外のときは がとして定義されます(1 次元の場合。高次元での定義については以下を参照)。これは基本的に、 が 0 に近づくにつれて が負の無限大に近づくという事実に依存しています。 ${\displaystyle g(x,b)}$${\displaystyle -\log(bx)}$${\displaystyle x<b}$${\displaystyle \infty}$${\displaystyle \logt}$${\displaystyle t}$

これにより、最適化される関数に勾配が導入され、 の極端でない値(この場合は より小さい値) が優先され、これらの極端から離れるにつれて関数に与える影響は比較的小さくなります。 ${\displaystyle x}$${\displaystyle b}$

最適化される関数によっては、計算コストの低い逆バリア関数よりも対数バリア関数が優先される場合があります。

各次元が独立していれば、高次元への拡張は簡単です。より厳密に低く制限される各変数に対して、 を追加します。 ${\displaystyle x_{i}}$${\displaystyle b_{i}}$${\displaystyle -\log(b_{i}-x_{i})}$

対象を最小限にする${\displaystyle \mathbf {c} ^{T}x}$${\displaystyle \mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m}$

厳密に実行可能であると仮定します。${\displaystyle \{\mathbf {x} |Ax<b\}\neq \emptyset }$

対数障壁を定義する ${\displaystyle g(x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}}$

• ペナルティ方式
• 拡張ラグランジアン法

• 講義 14: UCLAの Lieven Vandenberghe 教授によるバリアメソッド