手法の説明

ウィキペディア小見出し辞書

手法の説明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/12 04:49 UTC 版)

「準ニュートン法」の記事における「手法の説明」の解説

ニュートン法と同様、関数 f ( x ) の解を見つけるために二次の近似を用いる。 f ( x ) の二階のテイラー展開は f ( x k + Δ x ) ≈ f ( x k ) + ∇ f ( x k ) ⊺ Δ x + 1 2 Δ x ⊺ B Δ x となる。この式で ∇ f は勾配を表し、 B はヘッセ行列の近似を表す。勾配 ∇ f はさらに次のように近似される。 ∇ f ( x k + Δ x ) ≈ ∇ f ( x k ) + B Δ x この勾配が0になると仮定するとニュートン・ステップが次の式で計算される。 Δ x = − B − 1 ∇ f ( x k ) そこでヘッセ行列の近似 B は次の式を満たすように行われる。 ∇ f ( x k + Δ x ) = ∇ f ( x k ) + B Δ x この方程式はセカント方程式と呼ばれる。 f が多次元空間上で定義される関数のとき、この式から B を求める問題は劣決定問題になる(式の数よりも未知数の数が多い問題のこと)。このとき B を求めて、ニュートン・ステップにより解を更新するという処理はセカント方程式を解くことに帰着される。多くの準ニュートン法はセカント方程式の解の選び方が異なっている。ほとんどの方法では B = B ⊺ という対称性を仮定して解を求める。加えて、以下のリストに示す方法では新たな近似 B k + 1 を得るために、その前の近似 B k と、あるノルムの意味において近い解を選ぼうとする。すなわち何らかの正定値行列 V に対して B k + 1 = arg ⁡ min B ‖ B − B k ‖ V と成るように B を更新する。近似ヘッセ行列の初期値としては単位行列などが用いられる。最適化の解 x k は近似によって得られた B k を用いたニュートン・ステップにより更新される。 アルゴリズムをまとめると以下のようになる。 Δ x k = − α B k − 1 ∇ f ( x k ) x k + 1 = x k + Δ x k 新しい点での勾配 ∇ f ( x k + 1 ) を計算し y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) とする y k を用いてヘッセ行列の逆行列 B k + 1 − 1 を直接近似する。近似の式は各手法ごとに以下のリストの通り。 Method B k + 1 = H k + 1 = B k + 1 − 1 = DFP法（英語版） ( I − y k Δ x k ⊺ y k ⊺ Δ x k ) B k ( I − Δ x k y k ⊺ y k ⊺ Δ x k ) + y k y k ⊺ y k ⊺ Δ x k H k + Δ x k Δ x k ⊺ y k T Δ x k − H k y k y k ⊺ H k ⊺ y k ⊺ H k y k BFGS法 B k + y k y k ⊺ y k ⊺ Δ x k − B k Δ x k ( B k Δ x k ) ⊺ Δ x k T B k Δ x k ( I − y k Δ x k ⊺ y k ⊺ Δ x k ) ⊺ H k ( I − y k Δ x k ⊺ y k ⊺ Δ x k ) + Δ x k Δ x k ⊺ y k ⊺ Δ x k ブロイデン法 B k + y k − B k Δ x k Δ x k ⊺ Δ x k Δ x k ⊺ H k + ( Δ x k − H k y k ) Δ x k ⊺ H k Δ x k ⊺ H k y k Broyden family ( 1 − φ k ) B k + 1 BFGS + φ k B k + 1 DFP , φ ∈ [ 0 , 1 ] SR1法（英語版） B k + ( y k − B k Δ x k ) ( y k − B k Δ x k ) ⊺ ( y k − B k Δ x k ) ⊺ Δ x k H k + ( Δ x k − H k y k ) ( Δ x k − H k y k ) ⊺ ( Δ x k − H k y k ) ⊺ y k