Trust region approach involves constructing a model function mk that approximates the function f in the region, Δ, near the current point xk. The model mk is often a quadratic obtained by a Taylor Series expansion of the function around xk.
where Bk is an approximation of the Hessian.
The subproblem to be solved at each iteration in order to find the step length is minpmk(p), subject to ∥p∥ ≤ Δk. [Nocedal]
To select all minimizers in fitbenchmarking that use a trust region approach, use the algorithm type trust_region
.
Most widely used optimization algorithm, which uses the same Hessian approximation as Gauss-Newton but uses a trust region strategy instead of line search. As the Hessian approximation is the same as Gauss-Newton, convergence rate is similar.
For Levenberg-Marquardt, the model function mk, is chosen to be
So, for a spherical trust region, the subproblem to be solved at each iteration is
Levenberg-Marquardt uses a combination of gradient descent and Gauss-Newton method. When the solution pGN lies inside of the trust region Δ, then pGN also solves the sub-problem. Otherwise, the current iteration is far from the optimal value and so the search direction is determined using steepest descent, which performs better than Gauss-Newton when far from the minimum.
- Advantages:
- Robust (more so than Gauss-Newton).
- Avoids the weakness with Gauss-Newton that Jacobian must be full rank.
- Fast to converge.
- Good initial guess not required.
- Disadvantages:
- Similarly to Gauss-Newton, not good for large residual problems.
- Can be slow to converge if a problem has many parameters
- Nocedal
Jorge Nocedal, Stephen J. Wright (2006), Numerical Optimization
- Ranganathan
Ananth Ranganathan (2004), The Levenberg-Marquardt Algorithm, University of California, Santa Barbara