next up previous

2.5.1 Newton Methods Overview

Newton methods include several classes, including discrete Newton, quasi Newton (QN) (also termed variable metric), and truncated Newton (TN). Historically, the memory requirements and computation associated with solving a linear system directly have restricted Newton methods only: (1) to small problems, (2) to problems with special sparsity patterns, or (3) near a solution, after a gradient method has been applied. Fortunately, advances in computing technology and software are making the Newton approach feasible for a wide range of problems. Particularly, with advances in automatic differentiation [35,53], the appeal of these methods should increase further. Extensive treatments of Newton methods can be found in the literature ([16,23,30,45], for example) and only general concepts will be outlined here.

For large-scale applications, essentially two specific classes are emerging as the most powerful techniques: limited-memory quasi-Newton (LMQN) and truncated Newton methods. LMQN methods attempt to combine the modest storage and computational requirements of CG methods with the superlinear convergence properties of standard (i.e., full memory) QN methods. Similarly, TN algorithms attempt to retain the rapid quadratic convergence rate of classic Newton methods while making computational requirements feasible for large-scale functions.