Innumerical optimization, thenonlinear conjugate gradient method generalizes theconjugate gradient method tononlinear optimization. For a quadratic function${\displaystyle {\displaystyle f(x)}}$

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

the minimum of${\displaystyle f}$ is obtained when thegradient is 0:

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

Whereas linear conjugate gradient seeks a solution to the linear equation${\displaystyle {\displaystyle A^{T}Ax=A^{T}b}}$, the nonlinear conjugate gradient method is generally used to find thelocal minimum of a nonlinear function using itsgradient${\displaystyle {\mathrm{\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${\displaystyle {\displaystyle f(x)}}$ of${\displaystyle N}$ variables to minimize, its gradient${\displaystyle {\mathrm{\nabla }}_{x}f}$ indicates the direction of maximum increase.One simply starts in the opposite (steepest descent) direction:

${\displaystyle \mathrm{\Delta }{x}_0=-{\mathrm{\nabla }}_{x}f(x_0)}$

with an adjustable step length${\displaystyle {\displaystyle \alpha }}$ and performs aline search in this direction until it reaches the minimum of${\displaystyle {\displaystyle f}}$:

${\displaystyle {\displaystyle {\alpha }_0:=\arg \underset{\alpha }{min}f(x_0+\alpha \mathrm{\Delta }{x}_0)}}$,

${\displaystyle {\displaystyle x_1=x_0+{\alpha }_0\mathrm{\Delta }{x}_0}}$

After this first iteration in the steepest direction${\displaystyle {\displaystyle \mathrm{\Delta }{x}_0}}$, the following steps constitute one iteration of moving along a subsequent conjugate direction${\displaystyle {\displaystyle s_n}}$, where${\displaystyle {\displaystyle s_0=\mathrm{\Delta }{x}_0}}$:

1. Calculate the steepest direction:${\displaystyle \mathrm{\Delta }{x}_n=-{\mathrm{\nabla }}_{x}f(x_n)}$,
2. Compute${\displaystyle {\displaystyle {\beta }_n}}$ according to one of the formulas below,
3. Update the conjugate direction:${\displaystyle {\displaystyle s_n=\mathrm{\Delta }{x}_n+{\beta }_n{s}_{n-1}}}$
4. Perform a line search: optimize${\displaystyle {\displaystyle {\alpha }_n=\arg \underset{\alpha }{min}f(x_n+\alpha s_n)}}$,
5. Update the position:${\displaystyle {\displaystyle x_{n+1}=x_n+{\alpha }_n{s}_n}}$,

With a pure quadratic function the minimum is reached withinN iterations (excepting roundoff error), but a non-quadratic function will make slower progress. Subsequent search directions lose conjugacy requiring the search direction to be reset to the steepest descent direction at least everyN iterations, or sooner if progress stops. However, resetting every iteration turns the method intosteepest descent. The algorithm stops when it finds the minimum, determined when no progress is made after a direction reset (i.e. in the steepest descent direction), or when some tolerance criterion is reached.

Within a linear approximation, the parameters${\displaystyle {\displaystyle \alpha }}$ and${\displaystyle {\displaystyle \beta }}$ are the same as in thelinear conjugate gradient method but have been obtained with line searches.The conjugate gradient method can follow narrow (ill-conditioned) valleys, where thesteepest descent method slows down and follows a criss-cross pattern.

Four of the best known formulas for${\displaystyle {\displaystyle {\beta }_n}}$ are named after their developers:

• Fletcher–Reeves:^[1]

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

• Polak–Ribière:^[2]

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

• Hestenes–Stiefel:^[3]

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

• Dai–Yuan:^[4]

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

These formulas are equivalent for a quadratic function, but for nonlinear optimization the preferred formula is a matter of heuristics or taste. A popular choice is${\displaystyle {\displaystyle \beta =max\{0,{\beta }^{PR}\}}}$, which provides a direction reset automatically.^[5]

Algorithms based onNewton's method potentially converge much faster. There, both step direction and length are computed from the gradient as the solution of a linear system of equations, with the coefficient matrix being the exactHessian matrix (for Newton's method proper) or an estimate thereof (in thequasi-Newton methods, where the observed change in the gradient during the iterations is used to update the Hessian estimate). For high-dimensional problems, the exact computation of the Hessian is usually prohibitively expensive, and even its storage can be problematic, requiring${\displaystyle O(N^2)}$ memory (but see the limited-memoryL-BFGS quasi-Newton method).

The conjugate gradient method can also be derived usingoptimal control theory.^[6] In this accelerated optimization theory, the conjugate gradient method falls out as a nonlinearoptimal feedback controller,

${\displaystyle u=k(x,\dot{x}):=-{\gamma }_a{\mathrm{\nabla }}_{x}f(x)-{\gamma }_b\dot{x}}$

for thedouble integrator system,

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

The quantities${\displaystyle {\gamma }_a>0}$ and${\displaystyle {\gamma }_b>0}$ are variable feedback gains.^[6]

• Gradient descent
• Broyden–Fletcher–Goldfarb–Shanno algorithm
• Conjugate gradient method
• L-BFGS (limited memory BFGS)
• Nelder–Mead method
• Wolfe conditions

• Optimization algorithms and methods
• Gradient methods

• Articles with short description
• Short description is different from Wikidata