非線形共役勾配法
2次関数
f ( x ) = ‖ A x − b ‖ 2 {\displaystyle \displaystyle f(x)=\|Ax-b\|^{2}}
の最小値問題は、次のように勾配が0となる点を得れば解ける。
∇ x f = 2 A T ( A x − b ) = 0 {\displaystyle \nabla _{x}f=2A^{T}(Ax-b)=0} .
線形共役勾配法は線形方程式 A T A x = A T b {\displaystyle \displaystyle A^{T}Ax=A^{T}b} の求解に用いられるのに対して、非線形共役勾配法は、関数の極小値探索を勾配 ∇ x f {\displaystyle \nabla _{x}f} のみを用いて行う。この手法は、対象非線形関数が極小点近傍において近似的に2次関数的に振る舞う、すなわち極小点において2階微分可能でありかつ2階微分が非特異的である場合に適用可能である。
N 変数関数 f(x) が与えられたとき、その勾配 ∇ x f {\displaystyle \nabla _{x}f} はその関数を最も増大させる方向を示す。まずは、最急降下法と同じくその逆方向へと探索を行う。
Δ x 0 = − ∇ x f ( x 0 ) {\displaystyle \Delta x_{0}=-\nabla _{x}f(x_{0})}
この方向に直線探索を行うことによりf を最小とするようなステップ長 α を求める。