切断ニュートン法とは？わかりやすく解説

切断ニュートン法（せつだんニュートンほう、英: truncated Newton method）とは、Ron Dembo・Trond Steihaugによって提案された手法で^[1]、多数の独立変数を持つ非線形関数最適化のためのアルゴリズムの一種でありHessian-free最適化とも呼ばれている^[2]。切断ニュートン法はニュートン方程式を繰り返し近似的に解き、関数のパラメータを更新する反復最適化アルゴリズムである。ただしソルバー内部では反復回数が限られた回数を達すると切断^{[注釈 1]}する。そのため、切断ニュートン法が良好な性能を発揮させるためにはソルバー内部で有限回の反復で良好な近似を行う必要がある^[3]。切断ニュートン法では共役勾配法が内部の反復に用いられる手法の候補として提案・評価されている^[2]。また切断ニュートン法では内部のアルゴリズムに対して前処理することも重要な前提条件となる^[4]。

脚注

[脚注の使い方]

注釈

^ 英: truncated

出典

^ Dembo, Ron S.; Steihaug, Trond (1983). “Truncated-Newton algorithms for large-scale unconstrained optimization”. Mathematical Programming (Springer) 26 (2): 190–212. doi:10.1007/BF02592055. Dembo, Ron S.; Eisenstat, Stanley C.; Steihaug, Trond (1982). “Inexact newton methods”. SIAM Journal on Numerical Analysis 19 (2): 400–408. Bibcode: 1982SJNA...19..400D. doi:10.1137/0719025. JSTOR 2156954.
^ ^a ^b Martens, James (2010). Deep learning via Hessian-free optimization (PDF). Proc. International Conference on Machine Learning.
^ Nash, Stephen G. (2000). “A survey of truncated-Newton methods”. Journal of Computational and Applied Mathematics 124 (1–2): 45–59. Bibcode: 2000JCoAM.124...45N. doi:10.1016/S0377-0427(00)00426-X.
^ Nash, Stephen G. (1985). “Preconditioning of truncated-Newton methods”. SIAM J. Sci. Stat. Comput. 6 (3): 599–616. doi:10.1137/0906042.

参考文献

Grippo, L.; Lampariello, F.; Lucidi, S. (1989). “A Truncated Newton Method with Nonmonotone Line Search for Unconstrained Optimization”. J. Optimization Theory and Applications 60 (3): 401–419. doi:10.1007/BF00940345.
Nash, Stephen G.; Nocedal, Jorge (1991). “A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization”. SIAM J. Optim. 1 (3): 358–372. doi:10.1137/0801023.