非線形共役勾配法

数理最適化において、非線形共役勾配法（ひせんけいきょうやくこうばいほう、英: nonlinear conjugate gradient method）とは非線形最適化問題に共役勾配法を拡張したものをいう。

原理

2次関数

${\displaystyle \displaystyle f(x)=\|Ax-b\|^{2}}$

の最小値問題は、次のように勾配が0となる点を得れば解ける。

${\displaystyle \nabla _{x}f=2A^{T}(Ax-b)=0}$.

線形共役勾配法は線形方程式 ${\displaystyle \displaystyle A^{T}Ax=A^{T}b}$ の求解に用いられるのに対して、非線形共役勾配法は、関数の極小値探索を勾配 ${\displaystyle \nabla _{x}f}$のみを用いて行う。この手法は、対象非線形関数が極小点近傍において近似的に2次関数的に振る舞う、すなわち極小点において2階微分可能でありかつ2階微分が非特異的である場合に適用可能である。

N 変数関数 f(x) が与えられたとき、その勾配 ${\displaystyle \nabla _{x}f}$ はその関数を最も増大させる方向を示す。まずは、最急降下法と同じくその逆方向へと探索を行う。

${\displaystyle \Delta x_{0}=-\nabla _{x}f(x_{0})}$

この方向に直線探索を行うことによりf を最小とするようなステップ長 α を求める。

${\displaystyle \displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})}$

${\displaystyle \displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}}$

このように最初のイテレーションで最急方向 ${\displaystyle \Delta x_{0}}$ に降下した後は、以下の手順に従い、共役方向 ${\displaystyle \displaystyle s_{n}}$ を計算してその方向へと降下する。ここで、${\displaystyle \displaystyle s_{0}=\Delta x_{0}}$ とする。

1. 最急方向 ${\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})}$ を算出
2. 後述する式に従って ${\displaystyle \displaystyle \beta _{n}}$ を算出
3. 共役方向 ${\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}}$ を算出
4. 直線探索 ${\displaystyle \displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})}$ を行う
5. 位置を更新 ${\displaystyle \displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}}$

純粋な二次関数では、N 回反復すればかならず（丸め誤差を除いて）最小値に到達するが、非二次関数では収束はより遅くなる。後続の探索方向は共役性を失うため、最適化の進捗が止まる前に、少なくともＮ回反復する毎に探索方向を最急降下方向にリセットする必要がある。しかし、反復する毎に毎回リセットを行ってしまうと、最急降下法と変わらなくなってしまう。このアルゴリズムは、方向リセットをした後（すなわち最急降下方向）でも進捗がないとき、または何らかの許容基準に達したときに最小値を見つけたとみなして停止する。

線形近似の範囲内ではパラメータ α と β は線形共役勾配法と同一となるが、直線探索を用いて算出する。共役勾配法は、最急降下法ではジグザグパターンに陥ってしまい収束が遅くなってしまうような、狭い（ill-conditionな）谷に沿って最適化を進めることができる。

以下に示す4つの公式が β_n の算出方法として有名である。それぞれ、名前は開発者の名に因む。

• Fletcher–Reeves:^[1]

${\displaystyle \beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}$

• Polak–Ribière:^[2]

${\displaystyle \beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.}$

• Hestenes-Stiefel:^[3]

${\displaystyle \beta _{n}^{HS}=-{\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.}$

• Dai–Yuan:^[4]

${\displaystyle \beta _{n}^{DY}=-{\frac {\Delta x_{n}^{T}\Delta x_{n}}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}}$

これらの公式は2次関数に対しては全て同一となるが、非線形最適化問題に際してはヒューリスティクスもしくは好みにもとづいて選ばれる。${\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}}$ のように選ぶと、自動的に降下方向のリセットも行われるため普及している^[5]。

ニュートン法に基くアルゴリズムはより急速に収束する可能性がある。それらのアルゴリズムは勾配とヘッセ行列の厳密値（ニュートン法の場合）もしくは推定値（準ニュートン法の場合）を用いてステップ方向とステップ長の両方を線形方程式系を解いて求める。しかし、高次元の問題においてはヘッセ行列の厳密値の計算は実行不可能なほど計算コストが高く、また推定値でさえその格納には ${\displaystyle O(N^{2})}$ のメモリを要するため格納すら難しい場合がある。

関連項目

• BFGS法
• 共役勾配法
• L-BFGS法
• ネルダー–ミード法
• MODIFIED FLETCHER-REEVES-TYPE

脚注

出典

外部リンク

• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.
• A NONLINEAR CONJUGATE GRADIENT METHOD WITH A STRONG GLOBAL CONVERGENCE PROPERTY by Y. H. DAI and Y. YUAN.
• Different types of Nonlinear Conjugate Gradient （スペイン語）

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）