Newton's Method

298. Newton's Method

298.1. Newton’s Method

Newton’s method is an iterative numerical technique to find roots of a function (i.e., solutions to $𝑓 (𝑥) = 0$ ).

Step 1. At each step, approximate $𝑓 (𝑥)$ by its tangent line at the current guess $𝑥_{𝑘}$ :

𝑓 (𝑥) \approx 𝑓 (𝑥_{𝑘}) + 𝑓^{'} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘})

Step 2. Set this approximation equal to 0:

0 = 𝑓 (𝑥_{𝑘}) + 𝑓^{'} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘})

Step 3. Solve for $𝑥$ :

𝑥 = 𝑥_{𝑘} - \frac{𝑓 (𝑥_{𝑘})}{𝑓^{'} (𝑥_{𝑘})}

Step 4. This gives the update rule:

𝑥 = 𝑥_{𝑘} - \frac{𝑓 (𝑥_{𝑘})}{𝑓^{'} (𝑥_{𝑘})}

298.1.1. Newton’s Method for Nonlinear Optimization

Used to find the roots of the first derivative $𝑓^{'} (𝑥) = 0$ , which correspond to the local minima/maxima of the original function $𝑓 (𝑥)$ .

Finding stationary points of a function $𝑓 (𝑥)$ , i.e., points where the gradient (derivative) is zero:

1D: $𝑓^{'} (𝑥) = 0$
nD: $\nabla 𝑓 (𝐱) = 𝟎$

It can be derived from either linear approximation of the gradient or quadratic approximation of the function

298.1.1.1. 1D Linear Approximation

Start with the first-order (linear) Taylor expansion of the derivative around $𝑥_{𝑘}$ :

𝑓^{'} (𝑥_{𝑘 + 1}) \approx 𝑓^{'} (𝑥_{𝑘}) + 𝑓^{″} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘})

Stationary point condition: Set the derivative to zero to find a candidate minimum or maximum

0 = 𝑓^{'} (𝑥_{𝑘}) + 𝑓^{″} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘})

Solve for the next iterate $𝑥_{𝑘 + 1}$ :

𝑥_{𝑘 + 1} = 𝑥_{𝑘} - \frac{𝑓^{'} (𝑥_{𝑘})}{𝑓^{″} (𝑥_{𝑘})}

298.1.1.2. nD Linear Approximation

Start with the first-order (linear) Taylor expansion of the gradient around $𝑥_{𝑘}$ :

\nabla 𝑓 (𝐱_{𝑘 + 1}) \approx \nabla 𝑓 (𝐱_{𝑘}) + 𝐻_{𝑘} (𝐱_{𝑘 + 1} - 𝐱_{𝑘})

where $𝐻_{𝑘} = \nabla^{2} 𝑓 (𝐱_{𝑘})$ is the Hessian matrix

Stationary point condition: Set the gradient to zero to find a candidate minimum or maximum:

𝟎 = \nabla 𝑓 (𝐱_{𝑘}) + 𝐻_{𝑘} (𝐱 + (𝑘 + 1) - 𝐱_{𝑘})

Solve for the next iterate $𝐱_{𝑘 + 1}$ :

𝐱_{𝑘 + 1} = 𝐱_{𝑘} - 𝐻_{𝑘}^{- 1} \nabla 𝑓 (𝐱_{𝑘})

298.1.1.3. 1D Quadratic Approximation

Start with the second-order (quadratic) Taylor expansion of the function around $𝑥_{𝑘}$ :

𝑓_{𝑄} (𝑥) = 𝑓 (𝑥_{𝑘}) + 𝑓^{'} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘}) + \frac{1}{2} 𝑓^{″} (𝑥_{𝑘}) {(𝑥 - 𝑥_{𝑘})}^{2}

Minimize the quadratic approximation: Set the derivative of $𝑓_{𝑄} (𝑥)$ to zero:

\frac{d}{d 𝑥} 𝑓_{𝑄} (𝑥) = 𝑓^{'} (𝑥_{𝑘}) + 𝑓^{″} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘}) = 0

Solve for the next iterate $𝑥_{𝑘 + 1}$ :

𝑥_{𝑘 + 1} = 𝑥_{𝑘} - \frac{𝑓^{'} (𝑥_{𝑘})}{𝑓^{″} (𝑥_{𝑘})}

298.1.1.4. nD Quadratic Approximation

Start with the second-order (quadratic) Taylor expansion of the function around $𝑥_{𝑘}$ :

\begin{matrix} 𝑚_{𝑘} (𝐩) = 𝑓 (𝐱_{𝑘}) + \nabla {𝑓 (𝐱_{𝑘})}^{𝑇} 𝐩 + \frac{1}{2} 𝐩^{𝑇} 𝐻_{𝑘} 𝐩 \\ 𝐩 = 𝐱 - 𝐱_{𝑘} \end{matrix}

Minimize the quadratic approximation: Set the gradient of $𝑚_{𝑘} (𝐩)$ with respect to $𝐩$ to zero:

\nabla 𝑚_{𝑘} (𝐩) = \nabla 𝑓 (𝐱_{𝑘}) + 𝐻_{𝑘} 𝐩 = 𝟎

Solve for the step $𝐩_{𝑘}$ and next iterate $𝐱_{𝑘 + 1}$ :

𝐩_{𝑘} = - 𝐻_{𝑘}^{- 1} \nabla 𝑓 (𝐱_{𝑘}), 𝐱_{𝑘 + 1} = 𝐱_{𝑘} + 𝐩_{𝑘}

298.1.1.5. Quadratic Approximation

𝑓_{𝑄} (𝑥) = 𝑓 (𝑥_{𝑘}) + 𝑓^{'} (𝑥_{𝑘}) (𝑥 - 𝑥_{𝑘}) + \frac{1}{2} 𝑓^{″} (𝑥_{𝑘}) {(𝑥 - 𝑥_{𝑘})}^{2}

Example

𝑓 (𝑥) = 𝑥^{5} 𝑓^{'} (𝑥) = 5 𝑥^{4}

Hello

298.1.2. Multi-Dimensional

second-order iterative algorithm

uses both the

first derivative (gradient)
second derivative (Hessian)

Step 1. Start with initial guess $𝑥_{0}$

Step 2. At each iteration $𝑘$ :

Compute gradient $\nabla 𝑓 (𝑥_{𝑘})$
Compute Hessian $\nabla^{2} 𝑓 (𝑥_{𝑘})$
Update:

𝐱_{𝑘 + 1} = 𝐱_{𝑘} - {[\nabla^{2} 𝑓 (𝐱_{𝑘})]}^{- 1} \nabla 𝑓 (𝐱_{𝑘})

\nabla 𝑓 (𝐱_{𝑘}) = [\begin{matrix} \frac{𝜕 𝑓}{𝜕 𝑥_{1}} (𝐱_{𝑘}) \\ \frac{𝜕 𝑓}{𝜕 𝑥_{2}} (𝐱_{𝑘}) \\ ⋮ \\ \frac{𝜕 𝑓}{𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \end{matrix}] \in ℝ^{𝑛} \nabla^{2} 𝑓 (𝐱_{𝑘}) = [\begin{matrix} \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1}^{2}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{1}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2}^{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛} 𝜕 𝑥_{1}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2} 𝜕 𝑥_{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2}} (𝐱_{𝑘}) \end{matrix}] \in ℝ^{𝑛 \times 𝑛}

Instead of computing the inverse explicitly, we solve the linear system:

\nabla^{2} 𝑓 (𝐱_{𝑘}) 𝐩_{𝑘} = \nabla 𝑓 (𝐱_{𝑘})

[\begin{matrix} \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1}^{2}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{1}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2}^{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛} 𝜕 𝑥_{1}} (𝐱_{𝑘}) & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2} 𝜕 𝑥_{2}} (𝐱_{𝑘}) & \dots & \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2}} (𝐱_{𝑘}) \end{matrix}] [\begin{matrix} 𝑝_{1} \\ 𝑝_{2} \\ ⋮ \\ 𝑝_{𝑛} \end{matrix}] = [\begin{matrix} \frac{𝜕 𝑓}{𝜕 𝑥_{1}} (𝐱_{𝑘}) \\ \frac{𝜕 𝑓}{𝜕 𝑥_{2}} (𝐱_{𝑘}) \\ ⋮ \\ \frac{𝜕 𝑓}{𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \end{matrix}]

\begin{matrix} \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1}^{2}} (𝐱_{𝑘}) 𝑝_{1} + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{2}} (𝐱_{𝑘}) 𝑝_{2} + \dots + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{1} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) 𝑝_{𝑛} = \frac{𝜕 𝑓}{𝜕 𝑥_{1}} (𝐱_{𝑘}) \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{1}} (𝐱_{𝑘}) 𝑝_{1} + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2}^{2}} (𝐱_{𝑘}) 𝑝_{2} + \dots + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{2} 𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) 𝑝_{𝑛} = \frac{𝜕 𝑓}{𝜕 𝑥_{2}} (𝐱_{𝑘}) \\ ⋮ \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛} 𝜕 𝑥_{1}} (𝐱_{𝑘}) 𝑝_{1} + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2} 𝜕 𝑥_{2}} (𝐱_{𝑘}) 𝑝_{2} + \dots + \frac{𝜕^{2} 𝑓}{𝜕 𝑥_{𝑛}^{2}} (𝐱_{𝑘}) 𝑝_{𝑛} = \frac{𝜕 𝑓}{𝜕 𝑥_{𝑛}} (𝐱_{𝑘}) \end{matrix}

Then update:

𝐱_{𝑘 + 1} = 𝐱_{𝑘} - 𝐩_{𝑘}

Example

𝑓 (𝑥, 𝑦) = 𝑥^{2} + 𝑥 𝑦 + 𝑦^{2}

Step 1. Compute Gradient

\nabla 𝑓 (𝑥, 𝑦) = [\begin{matrix} \frac{𝜕 𝑓}{𝜕 𝑥} \\ \frac{𝜕 𝑓}{𝜕 𝑦} \end{matrix}] = [\begin{matrix} 2 𝑥 + 𝑦 \\ 𝑥 + 2 𝑦 \end{matrix}]

Step 2. Compute Hessian

\nabla^{2} 𝑓 (𝑥, 𝑦) = [\begin{matrix} \frac{𝜕^{2} 𝑓}{𝜕 𝑥^{2}} & \frac{𝜕^{2} 𝑓}{𝜕 𝑥 𝜕 𝑦} \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑦 𝜕 𝑥} & \frac{𝜕^{2} 𝑓}{𝜕 𝑦^{2}} \end{matrix}] =

Step 0. Setup

We want to minimize a function $𝑓 (𝑥, 𝑦)$

At some iteration $𝑘$ , we compute:

Gradient

𝑔 = \nabla 𝑓 (𝑥_{𝑘}, 𝑦_{𝑘}) = [\begin{matrix} 𝑔_{1} \\ 𝑔_{2} \end{matrix}]

Hessian

𝐻 = \nabla^{2} 𝑓 (𝑥_{𝑘}, 𝑦_{𝑘}) = [\begin{matrix} 𝑎 & 𝑏 \\ 𝑏 & 𝑐 \end{matrix}]

We need the Newton step vector $𝑝$ from:

𝐻 𝑝 = 𝑔

so that the update is:

[\begin{matrix} 𝑥_{𝑘 + 1} \\ 𝑦_{𝑘 + 1} \end{matrix}] = [\begin{matrix} 𝑥_{𝑘} \\ 𝑦_{𝑘} \end{matrix}] - 𝑝

Step 1. We need the Newton step $𝑝$ from:

[\begin{matrix} 𝑎 & 𝑏 \\ 𝑏 & 𝑐 \end{matrix}] [\begin{matrix} 𝑝_{1} \\ 𝑝_{2} \end{matrix}] = [\begin{matrix} 𝑔_{1} \\ 𝑔_{2} \end{matrix}]

Which is two equations:

\begin{matrix} 𝑎 𝑝_{1} + 𝑏 𝑝_{2} = 𝑔_{1} \\ 𝑏 𝑝_{1} + 𝑐 𝑝_{2} = 𝑔_{2} \end{matrix}

Step 2. Solve without inversion

This is a simple linear system.

For example, solve the first equation for $𝑝_{1}$ :

𝑝_{1} = \frac{𝑔_{1} - 𝑏 𝑝_{2}}{𝑎}

Plug into the second:

\begin{matrix} 𝑏 (\frac{𝑔_{1} - 𝑏 𝑝_{2}}{𝑎}) + 𝑐 𝑝_{2} = 𝑔_{2} \\ \frac{𝑏 𝑔_{1}}{𝑎} - \frac{𝑏^{2}}{𝑎} 𝑝_{2} + 𝑐 𝑝_{2} = 𝑔_{2} \\ (𝑐 = \frac{𝑏^{2}}{𝑎}) 𝑝_{2} = 𝑔_{2} - \frac{𝑏 𝑔_{1}}{𝑎} \\ 𝑝_{2} = \frac{𝑎 𝑔_{2} - 𝑏 𝑔_{1}}{𝑎 𝑐 - 𝑏^{2}} \end{matrix}

Then substitute back for $𝑝_{1}$ :

𝑝_{1} = \frac{𝑔_{1} - 𝑏 𝑝_{2}}{𝑎}

Step 3. Newton update

[\begin{matrix} 𝑥_{𝑘 + 1} \\ 𝑦_{𝑘 + 1} \end{matrix}] = [\begin{matrix} 𝑥_{𝑘} \\ 𝑦_{𝑘} \end{matrix}] - [\begin{matrix} 𝑝_{1} \\ 𝑝_{2} \end{matrix}]