準Newton法

これらのキーワードがハイライトされています：最適化 optimization

準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}}$