next up previous

2.4.5 Nonlinear Conjugate Gradient     continued...

The quality of line search in these nonlinear CG algorithms is crucial to preserve the mutual conjugacy property of the search directions and to ensure that each generated direction is one of descent. A technique known as restarting is typically used to preserve a linear convergence rate by resetting to the steepest descent direction, for example, after a given number of linear searches (e.g., n). Preconditioning may also be used as in the linear case to accelerate convergence.

In sum, the greatest virtues of CG methods are their modest storage and computational requirements (both order n), combined with much better convergence than SD. These properties have made them popular linear-solvers and minimization choices in many applications, perhaps the only candidates for very large problems. The linear CG is often applied to systems arising from discretizations of partial differential equations where the matrices are frequently positive-definite, sparse, and structured [20,25].