非線形共役勾配法

数値最適化において、非線形共役勾配法は共役勾配法を非線形最適化に一般化したものである。二次関数の場合${\displaystyle \displaystyle f(x)}$

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

最小値${\displaystyle f}$勾配が0のときに得られる値：

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

線形共役勾配法は線形方程式の解を求める ${\displaystyle \displaystyle A^{T}Ax=A^{T}b}$非線形共役勾配法は、一般的に非線形関数の勾配を用いて局所最小値を求めるために用いられる。${\displaystyle \nabla _{x}f}$単独で機能します。これは、関数が最小値付近でほぼ二次関数である場合に有効です。これは、関数が最小値で2回微分可能であり、かつその最小値における2階微分が非特異である場合に該当します。

関数が与えられた場合${\displaystyle \displaystyle f(x)}$の${\displaystyle N}$最小化する変数、その勾配${\displaystyle \nabla _{x}f}$これは最大増加方向を示しています。単純に反対方向（最も急な下降方向）から始めればよいのです。

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

歩幅調節可能${\displaystyle \displaystyle \alpha }$そして、この方向で最小値に達するまで線探索を実行します。${\displaystyle \displaystyle 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 \displaystyle \Delta x_{0}}$以下の手順は、次の共役方向に沿って移動する1回の反復を構成する。${\displaystyle \displaystyle s_{n}}$、 どこ${\displaystyle \displaystyle s_{0}=\デルタ 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回以内の反復で到達します (丸め誤差を除く) が、二次関数でない場合は、進行が遅くなります。後続の探索方向では共役性が失われるため、探索方向を少なくともN回ごとに、または進行が停止した場合はそれよりも早く、最急降下方向にリセットする必要があります。ただし、反復ごとにリセットすると、この方法は最急降下法になります。アルゴリズムは、最小値が見つかったときに停止します。最小値は、方向リセット後 (つまり、最急降下方向) に進行がなくなったとき、または何らかの許容基準に達したときに決定されます。

線形近似の範囲内では、パラメータは${\displaystyle \displaystyle \alpha }$そして${\displaystyle \displaystyle \beta }$これらは線形共役勾配法の場合と同じですが、線探索によって得られたものです。共役勾配法は狭い（条件の悪い）谷をたどることができますが、最急降下法では速度が低下し、交差パターンをたどります。

最もよく知られている4つの公式${\displaystyle \displaystyle \beta _{n}}$開発者の名前が付けられています。

• フレッチャー・リーブス: ^{[ 1 ]}

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

• ポラック＝リビエール：^{[ 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}}}.}$

• ヘステネス-シュティーフェル: ^{[ 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})}}.}$

• ダイユアン: ^{[ 4 ]}

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

これらの式は二次関数では同等ですが、非線形最適化の場合、好ましい式は経験則または好みの問題です。一般的な選択肢は${\displaystyle \displaystyle \beta =\max\{0,\beta ^{PR}\}}$方向を自動的にリセットします。^{[ 5 ]}

ニュートン法に基づくアルゴリズムは、収束速度がはるかに速い可能性があります。ニュートン法では、ステップの方向と長さの両方が、線形方程式系の解として勾配から計算されます。係数行列は、（ニュートン法の場合）正確なヘッセ行列、または（準ニュートン法の場合、反復中の勾配の変化がヘッセ行列の推定値の更新に使用される）その推定値です。高次元問題の場合、ヘッセ行列の正確な計算は通常、非常にコストがかかり、その保存も問題となる場合があり、${\displaystyle O(N^{2})}$メモリ（ただし、限定メモリL-BFGS準ニュートン法を参照）。

共役勾配法は最適制御理論を用いて導出することもできる。^{[ 6 ]}この加速最適化理論では、共役勾配法は非線形最適フィードバックコントローラとして現れる。

${\displaystyle u=k(x,{\dot {x}}):=-\gamma _{a}\nabla _{x}f(x)-\gamma _{b}{\dot {x}}}$

二重積分器システムの場合、

${\displaystyle {\ddot {x}}=u}$

数量$\gamma_a>0$ そして$\gamma_b>0$ 可変フィードバックゲインである。^{[ 6 ]}

• 勾配降下法
• ブロイデン・フレッチャー・ゴールドファーブ・シャノアルゴリズム
• 共役勾配法
• L-BFGS（限定メモリBFGS）
• ネルダー・ミード法
• ウルフの状況