バリア関数

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

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

対数バリア関数

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

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

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

高次元

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

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

脚注

参考文献

ウィキメディア・コモンズには、ニュートン法に関連するカテゴリがあります。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）