非線形共役勾配法
α 0 := arg  min α f ( x 0 + α Δ x 0 ) {\displaystyle \displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})} x 1 = x 0 + α 0 Δ x 0 {\displaystyle \displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}}
このように最初のイテレーションで最急方向 Δ x 0 {\displaystyle \Delta x_{0}} に降下した後は、以下の手順に従い、共役方向 s n {\displaystyle \displaystyle s_{n}} を計算してその方向へと降下する。ここで、 s 0 = Δ x 0 {\displaystyle \displaystyle s_{0}=\Delta x_{0}} とする。
最急方向 Δ x n = − ∇ x f ( x n ) {\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})} を算出
後述する式に従って β n {\displaystyle \displaystyle \beta _{n}} を算出
共役方向 s n = Δ x n + β n s n − 1 {\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}} を算出
直線探索 α n = arg  min α f ( x n + α s n ) {\displaystyle \displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})} を行う
位置を更新 x n + 1 = x n + α n s n {\displaystyle \displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}}
純粋な二次関数では、N 回反復すればかならず(丸め誤差を除いて)最小値に到達するが、非二次関数では収束はより遅くなる。後続の探索方向は共役性を失うため、最適化の進捗が止まる前に、少なくともN回反復する毎に探索方向を最急降下方向にリセットする必要がある。しかし、反復する毎に毎回リセットを行ってしまうと、最急降下法と変わらなくなってしまう。このアルゴリズムは、方向リセットをした後(すなわち最急降下方向)でも進捗がないとき、または何らかの許容基準に達したときに最小値を見つけたとみなして停止する。
線形近似の範囲内ではパラメータ α と β は線形共役勾配法と同一となるが、直線探索を用いて算出する。共役勾配法は、最急降下法ではジグザグパターンに陥ってしまい収束が遅くなってしまうような、狭い(ill-conditionな)谷に沿って最適化を進めることができる。