Trust-region methods – the Levenberg–Marquardt algorithm

Prince, E.; Boggs, P. T.

doi:10.1107/97809553602060000609

International
Tables for
Crystallography
Volume C
Mathematical, physical and chemical tables
Edited by E. Prince

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. C. ch. 8.1, p. 683

Section 8.1.4.2. Trust-region methods – the Levenberg–Marquardt algorithm

E. Prince^a and P. T. Boggs^b

^a NIST Center for Neutron Research, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA, and ^bScientific Computing Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA

8.1.4.2. Trust-region methods – the Levenberg–Marquardt algorithm

| top | pdf |

These remaining problems can be addressed by the utilization of a trust-region modification to the basic Gauss–Newton algorithm. For this procedure, we compute the step, d, as the solution to the linear least-squares problem subject to the constraint that $[\left \| {\bf d}\right \| \leq \tau _c]$ , where $[\tau _c]$ is the trust-region radius. Here, the linearized model is modified by admitting that the linearization is only valid within a limited region around the current approximation. It is clear that, if the trust region is sufficiently large, this constrained step will in fact be unconstrained, and the step will be the same as the Gauss–Newton step. If the constraint is active, however, the step has the form $[\lbrack {\bi J}({\bf x}_c)^T{\bi WJ}({\bf x}_c)+\mu {\bi I}]{\bf d}(\mu)={\bi J}({\bf x}_c){\bi W}[{\bf y}-{\bi M}({\bf x}_c)], \eqno (8.1.4.4)]$ where μ is the Lagrange multiplier corresponding to the constraint (see Section 8.3.1 ), that is, μ is the value such that $[\| {\bf d}(\mu)\| =\tau _c]$ . Formula (8.1.4.4) is known as the Levenberg–Marquardt equation. It can be seen from this formula that the step direction is intermediate between the Gauss–Newton direction and the direction of steepest descent, for which reason it is frequently known as ``Marquardt's compromise'' (Draper & Smith, 1981).

Efficient numerical calculation of d for a given value of μ is accomplished by noting that (8.1.4.4) is equivalent to the linear least-squares problem, find the minimum of $[S=\left \| \left ({{\bi J}( {\bf x}_c) \atop \sqrt {\mu }{\bi I}}\right) {\bf d}-\left ( {[{\bf y}-{\bi M}\left ({\bf x}_c\right)] \atop {\bi O}}\right) \right \| ^2. \eqno (8.1.4.5)]$ This problem can be solved by saving the QR factorization for μ = 0 and updating it for various values of μ greater than 0. The actual computation of μ is accomplished by a modified Newton method applied to the constraint equation (see Dennis & Schnabel, 1983, for details). Having calculated the constrained value of d, we set $[{\bf x}_{+}={\bf x}_c+{\bf d}]$ . The algorithm is completed by specifying a procedure for updating the trust-region parameter, τ_c, after each step. This is done by comparing the actual value of $[S({\bf x}_{+})]$ with the predicted value based on the linearization. If there is good agreement between these values, τ is increased. If there is not good agreement, τ is left unchanged, and if $[S({\bf x}_{+}) \, \gt \, S({\bf x}_c)]$ , the step is rejected, and τ is reduced. Global convergence can be shown under reasonable conditions, and very good computational performance has been observed in practice.

References

Dennis, J. E. & Schnabel, R. B. (1983). Numerical methods for unconstrained optimization and nonlinear equations. Englewood Cliffs, NJ: Prentice Hall.Google Scholar

Draper, N. & Smith, H. (1981). Applied regression analysis. New York: John Wiley.Google Scholar

International Tables for Crystallography (2006). Vol. C. ch. 8.1, p. 683