Levenberg–Marquardt algorithm

Remarks

Part 1 holds because $p^T (J^T J + \lambda I) p = \norm{J p}^2 + \lambda \norm{p}^2 > 0$ for $p \ne 0$. Part 2 follows: $g^T \delta = -g^T (J^T J + \lambda I)^{-1} g < 0$. For part 3, $\delta$ satisfies the optimality conditions of the ball-constrained problem with multiplier $\lambda \ge 0$, and the problem is convex. So the method is a trust region method for the Gauss–Newton model, with $\lambda$ controlling the radius. Parts 4 and 5 show that it interpolates between Gauss–Newton steps (small $\lambda$) and short steepest descent steps (large $\lambda$).

The algorithm updates $\lambda$ at each step. If the step reduces $S$ enough, it is accepted and $\lambda$ is decreased; otherwise it is rejected and $\lambda$ is increased. Marquardt proposed replacing $\lambda I$ by $\lambda \, \mathrm{diag}(J^T J)$, which makes the step invariant under rescaling of the variables. Example: with $m = n = 1$, $r(x) = x - 1$ and $x = 3$, one has $J = 1$, $g = 2$ and $\delta(\lambda) = -2/(1 + \lambda)$, which is the full Gauss–Newton step $-2$ at $\lambda = 0$ and shrinks as $\lambda$ grows.

Going deeper

For a student

The method is due to Kenneth Levenberg (1944) and Donald Marquardt (1963). It is the standard algorithm for small and medium nonlinear least squares problems, such as curve fitting and camera calibration. Its damped normal equations are the same equations as in Tikhonov regularization of the linearized problem.