# 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