バリア関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数学の一分野である、制約付き最適化問題におけるバリア関数(バリアかんすう、: Barrier function)とは、ある点が実行可能領域英語版の境界に近付くにつれて、その点での値が無限大へと近付くような連続関数のことを言う(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) を足せばよい。

形式的定義[編集]

次を最小化せよ: \bold c^Tx

次を仮定する: \bold a_i^T x \le b_i, i = 1,\ldots,m

次の、厳密な実行可能領域を仮定する: \{\bold x|A x < b\}\ne0

次の対数バリア関数を定義する \Phi(x) = \begin{cases}

\sum_{i=1}^m -\log(b_i - a_i^Tx) & \text{for } Ax<b \\
+\infty & \text{otherwise}
\end{cases}


参考文献[編集]

  • Nocedal, Jorge; and Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2. 
  • [1] lecture on barrier method.