ニュートン法

ニュートン法#

  • 読み: にゅーとんほう

  • 英名: Newton’s Method

一般の非線形方程式や最小化問題を解くための手法の一つであるが,ここでは無制約最小化問題を解くための手法としてのニュートン法について取り上げる.

無制約最小化問題に対するニュートン法の概要は以下の通りである.目的関数 \(f(x), \ x \in \mathbb{R}^n\) を点 \(x_k \in \mathbb{R}^n\) で 2 次近似したモデル関数の最小化を行い,探索方向を決定する.このためには \(\nabla^2 f(x_k)d = -\nabla f(x_k)\) という方程式を解けばよい.この方程式の解 \(d_k \in \mathbb{R}^n\) を探索方向として採用し,新たな点を決定する.以上の操作を停止条件が満たされるまで繰り返す.

ニュートン法は解の近くでは 2 次収束するという利点がある.しかし,ヘッセ行列の計算に時間をとられることにより収束までに時間が掛かってしまうことがある.また,初期点が解から離れていた場合には,解に収束しない可能性がある.さらに,目的関数が 2 階連続微分可能ではない場合や目的関数のヘッセ行列の正定値性が保証できない場合にはニュートン法は適用できないという問題がある.なお,これらの問題に対応するため,ヘッセ行列の近似行列を用い求解を行なう準ニュートン法や修正ニュートン法などの手法が提案されている.

関連