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

バルジライ・ボールウェイン法（バルジライ・ボールウェインほう、）とは、各反復において直前・直直前いずれかの反復での情報を用いてステップサイズを決定する手続きを持つ無制約最適化問題に対する最急降下法の一種である。バルジライ・ボールウェイン法やその改良版の解法では緩い条件の下で大域的収束性を示すことから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。バルジライ・ボールウェイン法は目的関数に依存せず手続きを行うため、線形・非線形方程式系に対する解法として用いることができる。

方法 点 において勾配 を用いて凸関数 を最小化する。ここで直前の二つの反復点における勾配 、 とすると、反復点は で求めることができる。ただし、 は直前の反復におけるステップサイズである（バルジライ・ボールウェイン法のステップサイズとは限らない）。ここで、、とおく。

バルジライ・ボールウェイン法の反復式は であり、ステップサイズ は以下のどちらかが選ばれる:

[long BB step] [short BB step]

バルジライ・ボールウェイン法はまた 、 のような方程式系に対して適用することができる。このとき のヤコビ行列は正定値行列であるとし、 が正である必要がある。

脚注

外部リンク Jonathan Barzilai