Chemistry - Gauss-Newton algorithm

In mathematics, the Gauss-Newton algorithm is used to solve nonlinear least squares problems. It is a modification of Newton's method that does not use second derivatives.

The problem

Given m functions f₁, ..., f_m of n parameters p₁, ..., p_n with m≥n, we want to minimize the sum

$S(p) = \sum_{i=1}^m (f_i(p))^2.$

Here, p stands for the vector (p₁, ..., p_n).

The algorithm

The Gauss-Newton algorithm is an iterative procedure. This means that the user has to provide an initial guess for the parameter vector p, which we will call p⁰.

Subsequent guesses p^k for the parameter vector are then produced by the recurrence relation

$p^{k+1} = p^k - (J_f(p^k)\,J_f(p^k)^\top)^{-1} J_f(p^k) \, f(p^k),$

where f=(f₁, ..., f_m) and J_f(p) denotes the Jacobian of f at p (note that J_f is not square).

The matrix inverse is never computed explicitly in practice. Instead, we use

p k + 1 = p k + δ k,

and we compute the update δ^k by solving the linear system

$J_f(p^k) \, J_f(p^k)^\top \, \delta^k = -J_f(p^k) \, f(p^k).$

A good implementation of the Gauss-Newton algorithm also employs a line search algorithm: instead of the above formula for p^k+1, we use

$p^{k+1} = p^k + \alpha^k \, \delta^k,$

where the number α^k is in some sense optimal.

Other algorithms

The recurrence relation for Newton's method for minimizing a function S is

p k + 1 = p k - [H (S)(p k)] - 1 J S (p k),

where $J S$ and $H (S)$ denote the Jacobian and Hessian of S respectively. Using Newton's method for our function $S(p) = \sum_{i=1}^m (f_i(p))^2$ gives $J_S(p) = 2 J_f(p)\,f(p)$ and

$H(S)(p) = 2 J_f(p) \, J_f(p)^\top + 2 \sum_{i=1}^m f_i(p) \, \nabla^2 f_i(p),\,$

where ∇² denotes the Laplacian. We can conclude that the Gauss-Newton method is the same as Newton's method with the Σ f ∇²f term ignored.

Other algorithms for solving least squares problems include the Levenberg-Marquardt algorithm and gradient descent.

Categories: Optimization algorithms