Nonlinear conjugate gradient method

There is a family of nonlinear conjugate gradient methods which generalize the conjugate gradient method to nonlinear optimization. Whereas linear conjugate gradient seeks a solution to the linear equation Ax=b, nonlinear conjugate gradient methods are generally used to find minima of some scalar-valued function, f of an affine point, x.

A few modifications are widely used.

Line search (determining α)

With a nonlinear function, it is generally not possible to determine the distance to travel along the direction at each step. Approaches include the secant method among others.

Determining β

There are two popular formulas to determine the beta coefficient: Fletcher–Reeves and Polak–Ribière:

• Fletcher–Reeves:

$\beta _{i+1}={\frac {r_{i+1}^{T}r_{i+1}}{r_{i}^{T}r_{i}}}$

• Polak–Ribière:

$\beta _{i+1}=\max \left({\frac {r_{i+1}^{T}(r_{i+1}-r_{i})}{r_{i}^{T}r_{i}}},0\right)$

References

The conjugate gradient method was originally proposed in

• Magnus R. Hestenes and Eduard Stiefel (1952), Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49, 409–436.

Descriptions of the method can be found in the following text books:

• Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
• Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Gene H. Golub and Charles F. Van Loan, Matrix computations (3rd ed.), Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.

External links

• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.