Newton-Raphson Method

The Newton-Raphson method (often simply called Newton’s method) is a powerful optimization technique that uses both first and second derivatives to find the minimum or maximum of a function. It is named after Isaac Newton and Joseph Raphson.

Principle

Newton’s method is based on using a quadratic approximation of the objective function at each iteration. For a function $L(\theta )$, the quadratic approximation around the current point ${\theta }_k$ is:

$L(\theta )\approx L({\theta }_k)+\nabla L({\theta }_k{)}^T(\theta -{\theta }_k)+\frac{1}{2}(\theta -{\theta }_k{)}^T\mathbf{H}({\theta }_k)(\theta -{\theta }_k)$

where $\nabla L$ is the gradient and $\mathbf{H}$ is the Hessian matrix.

Algorithm

Univariate Case (D=1)

For a function $L(\theta )$ with scalar variable $\theta$:

1. Start with an initial guess ${\theta }_0$
2. At each iteration $k$:
   • Compute the first derivative $L^{\prime }({\theta }_k)$
   • Compute the second derivative $L^{\prime \prime }({\theta }_k)$
   • Update: ${\theta }_{k+1}={\theta }_k-\frac{L^{\prime }({\theta }_k)}{L^{\prime \prime }({\theta }_k)}$
3. Stop when $|L^{\prime }({\theta }_k)|<\epsilon$ or $|{\theta }_{k+1}-{\theta }_k|<\epsilon$

The geometric interpretation is that we find the minimum of the parabola that approximates the function at the current point.

Multivariate Case (D≥2)

For a function $L(\theta )$ with vector variable $\theta \in {\mathbb{R}}^D$:

1. Start with an initial guess ${\theta }_0$
2. At each iteration $k$:
   • Compute the gradient $\mathbf{g}=\nabla L({\theta }_k)$
   • Compute the Hessian $\mathbf{H}={\nabla }^{2}L({\theta }_k)$
   • Solve the linear system: $\mathbf{H}\Delta \theta =-\mathbf{g}$
   • Update: ${\theta }_{k+1}={\theta }_k+\Delta \theta$
3. Stop when $||\mathbf{g}||<\epsilon$ or $||\Delta \theta ||<\epsilon$

This can also be written as: ${\theta }_{k+1}={\theta }_k-{\mathbf{H}}^{-1}\mathbf{g}$, though directly computing the inverse is generally avoided in practice due to numerical considerations.

Derivation

The derivation comes from setting the derivative of the quadratic approximation to zero:

$\nabla L(\theta )\approx \nabla L({\theta }_k)+\mathbf{H}({\theta }_k)(\theta -{\theta }_k)=0$

Solving for $\theta$ gives: $\theta ={\theta }_k-\mathbf{H}({\theta }_k{)}^{-1}\nabla L({\theta }_k)$

This becomes the update rule for the next iteration.

Convergence Properties

Newton’s method has excellent convergence properties when started sufficiently close to a solution:

• Quadratic convergence: The error approximately squares at each iteration
• Typically requires fewer iterations than gradient-based methods
• Invariant to linear transformations of parameters (unlike gradient descent)

However, convergence is only guaranteed under certain conditions:

• The Hessian must be positive definite at each iteration (for minimization)
• The initial point must be sufficiently close to a local minimum

Modified Newton Methods

To address potential issues with the basic Newton method:

Line Search

Introduce a step size parameter $\alpha$: ${\theta }_{k+1}={\theta }_k-\alpha {\mathbf{H}}^{-1}\mathbf{g}$

The step size $\alpha$ is chosen to ensure:

• Descent property: $L({\theta }_{k+1})<L({\theta }_k)$
• Appropriate step length via Wolfe conditions or Armijo rule

Hessian Modification

When the Hessian is not positive definite:

• Add a positive diagonal matrix: $\mathbf{H}+\lambda \mathbf{I}$ (becomes Levenberg-Marquardt method)
• Perform eigenvalue modification to ensure positive definiteness
• Use trust region approaches

Advantages

• Rapid convergence near the solution
• Scale-invariant (unlike gradient descent)
• Typically requires fewer iterations than first-order methods
• Particularly effective for quadratic or nearly quadratic functions

Disadvantages

• Requires computation of second derivatives
• Expensive for large-scale problems (O(D³) for the linear solve)
• May diverge if started far from the solution
• Not guaranteed to converge for non-convex functions

Example: Newton’s Method for a Quadratic Function

For a quadratic function $L(\theta )=\frac{1}{2}{\theta }^T\mathbf{Q}\theta +{\mathbf{b}}^T\theta +c$:

• Gradient: $\nabla L(\theta )=\mathbf{Q}\theta +\mathbf{b}$
• Hessian: $\mathbf{H}=\mathbf{Q}$ (constant)

Newton’s method becomes: ${\theta }_{k+1}={\theta }_k-{\mathbf{Q}}^{-1}(\mathbf{Q}{\theta }_k+\mathbf{b})=-{\mathbf{Q}}^{-1}\mathbf{b}$

For a positive definite $\mathbf{Q}$, Newton’s method finds the exact minimum in a single step!

Implementation Considerations

• For large-scale problems, avoid explicit Hessian computation and inversion
• Use iterative methods to solve the linear system $\mathbf{H}\Delta \theta =-\mathbf{g}$
• Consider quasi-Newton methods that approximate the Hessian
• Use careful line search to ensure convergence
• Monitor the conditioning of the Hessian

Related Pages

• Univariate Optimisation
• Multivariate Optimisation
• Quasi-Newton Methods
• Trust Region Methods
• Levenberg-Marquardt Method