7.1 Inexact Newton Methods¶
Recall that the basic Newton step \(p_k^N\) is obtained by solving the symmetric \(n \times n\) linear system
In this section, we describe techniques for obtaining approximations to \(p_k^N\) that are inexpensive to calculate but are good search directions or steps. These approaches are based on solving (1) by using the conjugate gradient method or the Lanczos method. We refer to this family of methods by the general name inexact Newton methods.
Local Convergence of Inexact Newton Methods¶
Most rules for terminating the iterative solver (1) are based on the residual
where \(p_k\) is the inexact Newton step. Usually we terminate the CG iterations when
where the sequence \(\{\eta_k\}\) with \(0 < \eta_k < 1\) is called the forcing sequence.
Theorem 7.1. Suppose that \(\nabla^2 f(x)\) exists and is continuous in a neighborhood of a minimizer \(x^*\), with \(\nabla^2 f(x^*)\) is positive definite. Consider the iteration \(x_{k+1} = x_k + p_k\) where \(p_k\) satisfies \(\lVert r_k \rVert \leq \eta_k \lVert \nabla f_k \rVert\), and assume that \(\eta_k \leq \eta\) for some constant \(\eta \in [0, 1)\). Then if the starting point \(x_0\) is sufficiently near \(x^*\), the sequence \(\{x_k\}\) converges to \(x^*\) and satisfies
for some constant \(\hat{\eta}\) with \(\eta < \hat{\eta} < 1\).
Theorem 7.2. Suppose that the conditions of Theorem 7.1 hold, and assume that the iterates \(\{x_k\}\) generated by the inexact Newton method converge to \(x^*\). Then the rate of convergence is superlinear if \(\eta_k \to 0\). If in addition, \(\nabla^2 f(x)\) is Lipschitz continous for \(x\) near \(x^*\) and if \(\eta_k = O(\lVert \nabla f_k \rVert)\), then the convergence is quadratic.