# 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$$.

$m_k(p) = f_k + \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p$

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

$m_k(p) = \frac{1}{2} \|r_k\|^2 + p^T J_k^T r_k + \frac{1}{2} p^T J_k^T J_k p$

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