Newton Iterative Method

Newton itertative method is typically used to find root of a given equality and to find a minimum of a convex and twice-differentiable function.

For finding the root of \(f(x) = 0\), the Newton method update root \(x\) using

\[ x_{k+1} = x_k - t\frac{f(x_k)}{\nabla f(x_k)} \]

For minimizing an unconstrainted convex function \(f(x)\), the Newton method update \(x\) using

\[ x_{k+1} = x_k - t\frac{\nabla f(x_k)}{\nabla^2 f(x_k)} \]

Root Finding

The Newton method can be derived and proved from Taylor expansion theory, which approximates \(f(x)\) at \(x\) with different orders of truncating errors.

Let \(x^*\) be the optimal solution of a root finding problem as follows:

\[ f(x) = 0 \tag{1} \]

The first-order approximation of the optimality \(f(x^*)\) at \(x\), would be:

\[ f(x^*) = f(x) + \nabla f(x)(x^* - x) \tag{2} \]

Since \(x^*\) is a solution to Eqn.(1), Eqn.(2) can be rewritten as:

\[ 0 = f(x) + \nabla f(x)(x^* - x) \tag{3} \]

\[ x^* = x - \frac{f(x)}{\nabla f(x)} \tag{4} \]

Therefore the above update rules can be used to find the optomal solution given tolerances. Numerically, a step size factor \(t\) is typically added as follows.

\[ x_{k+1} = x_k - t\frac{f(x_k)}{\nabla f(x_k)} \tag{5} \]

The stoping crietia can be:

\[ f(x_k) \le \epsilon \tag{6} \]

Unconstrained Minimization Probelm

Here we want to find the optimal solution of a convex and twice-differentiable function \(g(x)\) as follows:

\[ \min_x g(x) \]

Applying the Newton’s method for this optimziation problem is the same as find the root of \(\nabla g(x) = 0\) as the gradient vanishes at the optimal point of a convex and differentiable function.

Let \(f(x) = \nabla g(x)\), then we have

\[ x_{k+1} = x_k - t\frac{f(x_k)}{\nabla f(x_k)} = x_k -t \frac{\nabla g(x_k)}{\nabla^2 g(x_k)} \]

Newton Step

Newton step is known as:

\[ \Delta x_n = -\frac{\nabla g(x_k)}{\nabla^2 g(x_k)} \]

Newton Decrement

Define Newton decrement as

\[ \lambda(x) = (\nabla g(x)^T\nabla^2 g(x)^{-1}\nabla g(x))^{\frac{1}{2}} = (\Delta x_n^T\nabla^2 g(x)\Delta x_n)^{\frac{1}{2}} \]

Stopping Crietia

Using Newton’s updating rule to update \(x\) at each step, we can get the second-order approximation of the funcation \(g\) at \(x\):

\[ g(x_{k+1}) = g(x_k) + \nabla g(x_k)\Delta x_n +\frac{1}{2} \Delta x_n \nabla^2 g(x_k) \Delta x_n \]

Thus the function evaluation error between steps is:

\[ g(x_{k+1}) - g(x_k) = \nabla g(x_k)\Delta x_n +\frac{1}{2} \Delta x_n \nabla^2 g(x_k) \Delta x_n = -\frac{1}{2}\lambda(x_k)^2 \]

Therefore controlling Newton decrement can help stop the iterations.

\[ \frac{1}{2}\lambda(x_k)^2 <= \epsilon \]

Equality Constrained Minimization Problem

Newton’s method can also be extended to solve the following equality constrained problem:

\[\begin{split} \min_x \ f(x) \\ \text{s.t.} \ Ax=b \end{split}\]