準Newton法 (quasi-Newton method)

k次元のベクトル \(\mathbf{x}\) 関数 \(f(\mathbf{x})\) の極大値や極小値を求める方法.Newton法Hesse行列逆行列を近似でおきかえて逆行列の計算を避ける.以下は極小値を求める方法. 初期値 \(\mathbf{x}_0\) から次の手続きを反復する

  • 探索方向の計算 \(\mathbf{d}_n=- H_n \nabla f(\mathbf{x}_n)\),ただし \(H\) は正定値対称行列
  • \(t_n=\arg\min_{t\ge 0}f(\mathbf{x}_n+t\mathbf{d}_n)\) を達成するような \(\mathbf{x}_{n+1}=\mathbf{x}_n+t_n\mathbf{d}_n\)に更新. \(n\) を一つ増やす.

\(\mathbf{x}_n\) が収束したとき,極小値は \(f(\mathbf{x}_n)\) になる.

\(H_n\) の更新法で代表的なのは BFGS法 (Broyden-Fletcher-Goldfarb-Shanno method; BFGS method) \[H_{n+1}=H_n+\frac{\mathbf{p}\mathbf{p}^\top}{\mathbf{p}^\top\mathbf{v}}-\frac{(H_n\mathbf{v})\mathbf{v}^\top H_n}{\mathbf{v}^\top H_n\mathbf{v}}+(\mathbf{v}^\top H_n\mathbf{v})\mathbf{u}\mathbf{u}^\top\] ただし \[\mathbf{p}=\mathbf{x}_{n+1}-\mathbf{x}_n\] \[\mathbf{v}=\nabla f(\mathbf{x}_{n+1})-\nabla f(\mathbf{x}_n)\] \[\mathbf{u}=\frac{\mathbf{p}}{\mathbf{p}^\top\mathbf{v}}-\frac{H_n\mathbf{v}}{{\mathbf{v}^\top }H_n\mathbf{v}}\]

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:58 (2493d)