バルジライ・ボールウェイン法

テンプレート:Expand English

バルジライ・ボールウェイン法（バルジライ・ボールウェインほう、テンプレート:Lang-en-short）とは、各反復において直前・直直前いずれかの情報を用いてステップサイズを決定し、反復を行う無制約最適化問題に対する最急降下法である。バルジライ・ボールウェイン法やその改良版の解法では緩い条件の下で大域的収束性を示すことから^[1]^[2]、様々な問題に対して共役勾配法などと比較しても優れた性能を示している^[3]。バルジライ・ボールウェイン法は目的関数に依存せず手続きを行うため、線形・非線形方程式系に対する解法として用いることができる。

方法

点 $x$ において勾配 $g$ を用いて凸関数 $f : ℝ^{n} \to ℝ$ を最小化する。ここで直前の二つの反復点における勾配 $g_{k - 1} (x_{k - 1})$ 、 $g_{k} (x_{k})$ とすると、反復点は $x_{k} = x_{k - 1} - α_{k - 1} g_{k - 1}$ で求めることができる。ただし、 $α_{k - 1}$ は直前の反復におけるステップサイズである（バルジライ・ボールウェイン法のステップサイズとは限らない）。ここで、 $Δ x = x_{k} - x_{k - 1}$ 、 $Δ g = g_{k} - g_{k - 1}$ とおく。

バルジライ・ボールウェイン法の反復式は $x_{k + 1} = x_{k} - α_{k} g_{k}$ であり、ステップサイズ $α_{k}$ は以下のどちらかが選ばれる:

[long BB step] $α_{k}^{L O N G} = \frac{Δ x \cdot Δ x}{Δ x \cdot Δ g}$
[short BB step] $α_{k}^{S H O R T} = \frac{Δ x \cdot Δ g}{Δ g \cdot Δ g}$

バルジライ・ボールウェイン法はまた $g (x) = 0$ 、 $g : ℝ^{n} \to ℝ^{n}$ のような方程式系に対して適用することができる。このとき $g$ のヤコビ行列は正定値行列であるとし、 $Δ x \cdot Δ g$ が正である必要がある。

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

外部リンク

Jonathan Barzilai

テンプレート:最適化アルゴリズムテンプレート:Math-stub

↑ テンプレート:Cite journal
↑ Raydan, M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM Journal of Optimization 7, pp 26-33. 1997
↑ Fletcher, R. (2005). "On the Barzilai–Borwein Method". In Qi, L.; Teo, K.; Yang, X. (eds.). Optimization and Control with Applications. Applied Optimization. Vol. 96. Boston: Springer. pp. 235–256. ISBN 0-387-24254-6

[:1-1] テンプレート:Cite journal

[:2-2] Raydan, M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM Journal of Optimization 7, pp 26-33. 1997

[:0-3] Fletcher, R. (2005). "On the Barzilai–Borwein Method". In Qi, L.; Teo, K.; Yang, X. (eds.). Optimization and Control with Applications. Applied Optimization. Vol. 96. Boston: Springer. pp. 235–256. ISBN 0-387-24254-6

[1]

[2]

[3]

バルジライ・ボールウェイン法

方法

脚注

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー