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.