バリア機能

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

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

モチベーション

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

f

(

x

)

を最小化する

x

\leq

b

を条件とする

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

f (x) + c (x)

を最小化する、

ここで、

x

>

b

の場合は

c (x) = \infty

、それ以外の場合は 0 となります。

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

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

f

(

x

) +

μ

g

(

x

)

を最小化する

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

対数バリア関数

対数バリア関数において、のときはが、それ以外のときはが定義されます（1次元の場合。高次元での定義については後述）。これは基本的に、が 0 に近づくにつれてが負の無限大に近づくという事実に基づいています。 $g(x,b)$ $-\log(bx)$ $x<b$ $\infty$ $\log t$ $t$

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

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

高次元

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

正式な定義

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

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

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

参照

参考文献

^ Nesterov, Yurii (2018). Lectures on Convex Optimization (第2版). Cham, Switzerland: Springer. p. 56. ISBN 978-3-319-91577-7。
^ Nocedal, Jorge; Wright, Stephen (2006).数値最適化（第2版）. ニューヨーク：Springer. p. 566. ISBN 0-387-30303-0。
^ Vanderbei, Robert J. (2001).線形計画法：基礎と拡張. Kluwer. pp. 277– 279.

外部リンク

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

[1] Nesterov, Yurii (2018). Lectures on Convex Optimization (第2版). Cham, Switzerland: Springer. p. 56. ISBN 978-3-319-91577-7。

[2] Nocedal, Jorge; Wright, Stephen (2006).数値最適化（第2版）. ニューヨーク：Springer. p. 566. ISBN 0-387-30303-0。

[3] Vanderbei, Robert J. (2001).線形計画法：基礎と拡張. Kluwer. pp. 277– 279.