In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function f ( x ) {\displaystyle \displaystyle f(x)}
f ( x ) = ‖ A x − b ‖ 2 , {\displaystyle \displaystyle f(x)=\|Ax-b\|^{2},}
the minimum of f {\displaystyle f} is obtained when the gradient is 0:
∇ x f = 2 A T ( A x − b ) = 0 {\displaystyle \nabla _{x}f=2A^{T}(Ax-b)=0} . Whereas linear conjugate gradient seeks a solution to the linear equation
A T A x = A T b {\displaystyle \displaystyle A^{T}Ax=A^{T}b} , the nonlinear conjugate gradient method is generally used to find the local minimum of a nonlinear function using its gradient ∇ x f {\displaystyle \nabla _{x}f} alone. It works when the function is approximately quadratic near the minimum, which is the case when the function is twice differentiable at the minimum and the second derivative is non-singular there. Given a function f ( x ) {\displaystyle \displaystyle f(x)} of N {\displaystyle N} variables to minimize, its gradient ∇ x f {\displaystyle \nabla _{x}f} indicates the direction of maximum increase. One simply starts in the opposite (steepest descent) direction:
Δ x 0 = − ∇ x f ( x 0 ) {\displaystyle \Delta x_{0}=-\nabla _{x}f(x_{0})}
with an adjustable step length α {\displaystyle \displaystyle \alpha } and performs a line search in this direction until it reaches the minimum of f {\displaystyle \displaystyle f} :
α 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}}
After this first iteration in the steepest direction Δ x 0 {\displaystyle \displaystyle \Delta x_{0}} , the following steps constitute one iteration of moving along a subsequent conjugate direction s n {\displaystyle \displaystyle s_{n}} , where s 0 = Δ x 0 {\displaystyle \displaystyle s_{0}=\Delta x_{0}} :
Calculate the steepest direction: Δ x n = − ∇ x f ( x n ) {\displaystyle \Delta x_{n}=-\nabla _{x}f(x_{n})} , Compute β n {\displaystyle \displaystyle \beta _{n}} according to one of the formulas below, Update the conjugate direction: s n = Δ x n + β n s n − 1 {\displaystyle \displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}}
… excerpt ends here. Continue reading the full article.
