バリア関数

数学の一分野である、制約付き最適化問題におけるバリア関数（バリアかんすう、英: Barrier function、障壁関数^[1]、しょうへきかんすう）とは、ある点が実行可能領域の境界に近付くにつれて、その点での値が無限大へと近付くような連続関数のことを言う（Nocedal and Wright 1999）。制約違反に対する罰則項として用いられる。最も一般的な二種類のバリア関数は、逆バリア関数と対数バリア関数である。対数バリア関数は、主双対内点法との関連で、再び興味を集めるものとなった。

関数 f(x) を最適化するとき、ある定数 $b$ に対して代わりに関数 $f(x)+g(x,b)$ を最適化することによって、変数 $x$ をつねに $b$ よりも厳密に小とすることができる。ここで、 $g(x,b)$ はバリア関数である。

対数バリア関数

対数バリア関数 $g(x,b)$ は、 $x<b$ の場合 $-\log(b-x)$ で、それ以外の場合では $\infty$ となる関数として定義される（但し 1 次元の場合。より高い次元の場合は下記参照）。この定義は本質的には、 $t$ が 0 に向かうにつれて $log(t)$ が負の無限大へと発散する事実に由来する。

この定義は $x$ の極値（この場合、値は $b$ より小さい）がより少ないものを好むように最適化され、一方で極値から離れた関数に対してはあまり影響を与えないような、関数への勾配を導入するものである。

対数バリア関数は、最適化される関数に依存して、計算的に高価値でない逆バリア関数よりも、好まれるものであるかも知れない。

高次元

高次元への拡張は、各次元が独立である限り、簡単なものである。 $b_{i}$ よりも厳密に小さいように制限された各変数 $a_{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 0$

次の対数バリア関数を定義する $\Phi (x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}$

脚注

[脚注の使い方]

^ 寒野善博 2019, p. 74.

参考文献

Nocedal, Jorge; and Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2
寒野善博著、駒木文保編『最適化手法入門』講談社、2019年。ISBN 978-4-06-517008-3。
lecture on barrier method.^{[リンク切れ]}