バリア関数のソースを表示

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

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

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

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

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

=== 高次元 ===
高次元への拡張は、各次元が独立である限り、簡単なものである。<math>b_i</math> よりも厳密に小さいように制限された各変数 <math>a_i</math> に対して、<math>-\log(b_i-x_i)</math> を足せばよい。

=== 形式的定義 ===
次を最小化せよ:<math> \mathbf c^Tx</math>

次を仮定する: <math>\mathbf a_i^T x \le b_i, i = 1,\ldots,m</math>

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
{{Commons category|Newton Method|ニュートン法}}
{{Refbegin}}
* {{Cite book|title = Numerical Optimization | first=Jorge| last = Nocedal | coauthors= and Stephen Wright| year=1999 | publisher=Springer | location=New York, NY| isbn=0-387-98793-2}}
* {{Cite book |和書 |author=寒野善博 |editor=駒木文保 |year=2019 |title=最適化手法入門 |publisher=講談社 |locate=東京 |isbn=978-4-06-517008-3 |ref=harv }}
* [http://www.ee.ucla.edu/ee236a/lectures/barrier.pdf lecture on barrier method.]{{リンク切れ|date=2015年12月}}
{{Refend}}

{{最適化アルゴリズム}}
{{Applied-math-stub}}
{{DEFAULTSORT:はりあかんすう}}
[[Category:関数]]
[[Category:関数の種類]]
[[Category:最適化]]
[[Category:数学に関する記事]]