4.1.8 Trust Region Method

The trust region methods take a different approach in selecting the next iteration step than the step length based method discussed in the previous section. Here the next point is calculated by first choosing some tentative step length and then applying the quadratic model to determine a direction and an actual step.

The trust region step can be calculated by the equation

$$( {\mathop{\nabla }\nolimits ^2 f(\vec{x})} + \lambda \mathcal{I}) \vec{p} + {\mathop{\nabla }\nolimits f(\vec{x})} = 0$$ (4.26)

where $\lambda$ is a nonnegative scalar and $\mathcal{I}$ is the identity matrix [35].

The value of $\lambda$ and consequently the size of the trust region is adapted by the quality of the previous evaluations.

Having solved the trust region problem, one must decide whether to accept the step or change the trust region radius and calculate a new solution.

In general an improvement of the target function is reflected in a decrease of $\lambda$ and vice versa. So if the trial step does not reduce the value of the target function, the value of $\lambda$ is modified and a new trial point is calculated from (4.26).

For $\lambda = 0$ the solution of (4.26) is simply the Newton direction, and for $\lambda \rightarrow \infty$ the step $\vec{p}$ becomes parallel to the steepest-descent direction.

A trust region method is used in the Levenberg-Marquardt algorithm described in Section 4.3.2.