Trust Region
Trust region approach involves constructing a model function \(m_k\) that approximates the function \(f\) in the region, \(\Delta\), near the current point \(x_k\). The model \(m_k\) is often a quadratic obtained by a Taylor Series expansion of the function around \(x_k\).
where \(B_k\) is an approximation of the Hessian.
The subproblem to be solved at each iteration in order to find the step length is \(\min_p m_k(p)\), subject to \(\|p\| \leq \Delta_k\). [Nocedal]
To select all minimizers in fitbenchmarking that use a trust region approach, use the algorithm type trust_region
.
Levenberg-Marquardt (levenberg-Marquardt
)
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 \(m_k\), is chosen to be
So, for a spherical trust region, the subproblem to be solved at each iteration is \(\min_p \frac{1}{2} \|J_k p + r_k\|^2\), subject to \(\|p\| \leq \Delta_k\).
Levenberg-Marquardt uses a combination of gradient descent and Gauss-Newton method. When the solution \(p^{GN}\) lies inside of the trust region \(\Delta\), then \(p^{GN}\) 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(1,2)
Jorge Nocedal, Stephen J. Wright (2006), Numerical Optimization
- Ranganathan
Ananth Ranganathan (2004), The Levenberg-Marquardt Algorithm, University of California, Santa Barbara