## File: Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt.html

package info (click to toggle)
gsl-ref-html 2.3-1
• area: non-free
• in suites: bullseye, buster, sid
• size: 6,876 kB
• ctags: 4,574
• sloc: makefile: 35
 file content (114 lines) | stat: -rw-r--r-- 5,883 bytes parent folder | download
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114  GNU Scientific Library – Reference Manual: Nonlinear Least-Squares TRS Levenberg-Marquardt

39.2.1 Levenberg-Marquardt

There is a theorem which states that if \delta_k is a solution to the trust region subproblem given above, then there exists \mu_k \ge 0 such that

( B_k + \mu_k D_k^T D_k ) \delta_k = -g_k

with \mu_k (\Delta_k - ||D_k \delta_k||) = 0. This forms the basis of the Levenberg-Marquardt algorithm, which controls the trust region size by adjusting the parameter \mu_k rather than the radius \Delta_k directly. For each radius \Delta_k, there is a unique parameter \mu_k which solves the TRS, and they have an inverse relationship, so that large values of \mu_k correspond to smaller trust regions, while small values of \mu_k correspond to larger trust regions.

With the approximation B_k \approx J_k^T J_k, on each iteration, in order to calculate the step \delta_k, the following linear least squares problem is solved:

[J_k; sqrt(mu_k) D_k] \delta_k = - [f_k; 0]

If the step \delta_k is accepted, then \mu_k is decreased on the next iteration in order to take a larger step, otherwise it is increased to take a smaller step. The Levenberg-Marquardt algorithm provides an exact solution of the trust region subproblem, but typically has a higher computational cost per iteration than the approximate methods discussed below, since it may need to solve the least squares system above several times for different values of \mu_k.