Newton-Raphson Method

The problem of finding the minima of a function can be reduced to the problem of finding the zeros of a function, specifically the first derivative of the cost function $S$.

Let $\mathbf{g}: \mathbb{R}^{m} \mapsto \mathbb{R}^{n}$ be a differentiable multivariate function whose

$$\mathbf{g}(\mathbf{x})=\mathbf{0}$$ (4.29)

is to be found. Expanding function $\mathbf{g}$ in a Taylor series locally around a suitable point $\mathbf {x}$ gives

$$\mathbf{g}(\mathbf{x} + \boldsymbol\delta) = \mathbf{g}(\ma... ...}) + \mathbf{J}_{g} \boldsymbol\delta + O(\boldsymbol\delta^2)$$ (4.30)

where $\mathbf{J}_{g}$ is the $n \times m$ matrix, the Jacobian of function $\mathbf{g}$ evaluated at $\mathbf {x}$.

The objective is to modify the value of $\mathbf {x}$ by an amount $\boldsymbol\delta$ such that the cost function evaluated at $\mathbf{x}_t + \boldsymbol\delta$ is exactly zero. Ignoring terms of order higher than $\boldsymbol\delta^{2}$, the estimate of $\boldsymbol\delta$ that, to first order, brings the function $\mathbf{g}$ closer to zero is the solution of the linear system (4.30) subject to the condition (4.29), namely

$$\mathbf{J}_{g} \boldsymbol\delta = - \mathbf{g}(\mathbf{x})$$ (4.31)

This system, provided that $\mathbf{J}_{g}$ has full rank, is a simple, possibly overdetermined linear system that can be solved using one of the techniques presented in Section 1.1. The idea behind iterative methods is to modify the point $\mathbf{x}_t$ by the quantity $\boldsymbol\delta_t$

$$\mathbf{x}_{t+1} = \mathbf{x}_t + \boldsymbol\delta_t$$ (4.32)

at iteration $t=1,2,\ldots$, computed so as to progressively approach the zero of the function.

In the single-variable case $n=m=1$, Newton's method reduces to

$$x_{t+1} = x_t - \dfrac{g(x)}{g'(x)}$$ (4.33)

In numerical analysis, this is the so-called Newton method (or Newton-Raphson method) for finding the zeros of a function.

The maxima and minima of a function are points at which the gradient can be set to zero. This technique can therefore be applied to find the maxima and minima of a function $f(\mathbf{x}): \mathbb{R}^{m} \mapsto \mathbb{R}$ by defining

$$\begin{array}{l} \mathbf{g}(\mathbf{x}) = \nabla f(\mathbf... ...bf{J}_g(\mathbf{x}) = \mathbf{H}_f(\mathbf{x}) \\ \end{array}$$ (4.34)

where $\nabla f(\mathbf{x})$ is the gradient function $\mathbb{R}^{m} \mapsto \mathbb{R}^{m}$, while $\mathbf{H}_f(\mathbf{x})$ is the Hessian matrix $m \times m$; these are the gradient and Hessian functions of $f$ evaluated at $\mathbf {x}$. Newton's update of the point $\mathbf {x}$ therefore becomes

$$\mathbf{H}_f(\mathbf{x}) \boldsymbol\delta_t = - \nabla f(\mathbf{x})$$ (4.35)

When used for optimization, Newton's method effectively approximates the function $f(\mathbf{x})$ in the neighborhood of $\mathbf {x}$ with a quadratic function. If $f(\mathbf{x})$ is a quadratic function, convergence is guaranteed in a single iteration.

Now, in the specific case of optimization methods, the function $f(\mathbf{x})$ is the cost function $S(\boldsymbol\beta)$. Therefore, when the Hessian matrix of $S(\boldsymbol\beta)$ is nonsingular, the parameter update equation

$$\boldsymbol\delta_t = -\mathbf{H}_{S}^{-1}(\boldsymbol\beta_t) \nabla S(\boldsymbol\beta_t)$$ (4.36)

is obtained through Newton's optimization method.