Newton Iterative Method

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:

\begin{matrix} (1) & f (x) = 0 \end{matrix}

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

\begin{matrix} (2) & f (x^{*}) = f (x) + \nabla f (x) (x^{*} - x) \end{matrix}

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

\begin{matrix} (3) & 0 = f (x) + \nabla f (x) (x^{*} - x) \end{matrix}

\begin{matrix} (4) & x^{*} = x - \frac{f (x)}{\nabla f (x)} \end{matrix}

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.

\begin{matrix} (5) & x_{k + 1} = x_{k} - t \frac{f (x_{k})}{\nabla f (x_{k})} \end{matrix}

The stoping crietia can be:

\begin{matrix} (6) & f (x_{k}) \leq ϵ \end{matrix}

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:

Δ x_{n} = - \frac{\nabla g (x_{k})}{\nabla^{2} g (x_{k})}

Newton Decrement#

Define Newton decrement as

λ (x) = (\nabla g (x)^{T} \nabla^{2} g (x)^{- 1} \nabla g (x))^{\frac{1}{2}} = (Δ x_{n}^{T} \nabla^{2} g (x) Δ 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}) Δ x_{n} + \frac{1}{2} Δ x_{n} \nabla^{2} g (x_{k}) Δ x_{n}

Thus the function evaluation error between steps is:

g (x_{k + 1}) - g (x_{k}) = \nabla g (x_{k}) Δ x_{n} + \frac{1}{2} Δ x_{n} \nabla^{2} g (x_{k}) Δ x_{n} = - \frac{1}{2} λ (x_{k})^{2}

Therefore controlling Newton decrement can help stop the iterations.

\frac{1}{2} λ (x_{k})^{2} <= ϵ

Equality Constrained Minimization Problem#

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

\begin{array}{r} min_{x} f (x) \\ s.t. A x = b \end{array}