what is the trust region algorithm in optimization?

Question

I see some books that say the trust region work with contour's line .but i can't understand

how choose the point with contour's line and sort them?

thank you if answer me.

Answer 1

Nocedal/Wright propose in Numerical Optimization (1999) on p.68 the following pseudo-code for iteratively setting the size of the trust-region:

Algorithm 4.1 (Trust Region).
Given $\bar\Delta > 0, \Delta_0 \in (0,\bar{\Delta})$, and $\eta \in [0, \frac{1}{4})$:
for $k=0,1,2,...$
$\qquad$ Obtain $p_k$ by approximately solving the [the optimization problem];
$\qquad$ Evaluate $\rho_k = \frac{f(x_k)-f(x_k + p_k)}{m_k(0)-m_k(p_k)}$;
$\qquad$ if $\rho_k < \frac{1}{4}$
$\qquad\qquad \Delta_{k+1} = \frac{1}{4}\lVert p_k \rVert$
$\qquad$ else
$\qquad\qquad$ if $\rho_k > \frac{3}{4}$ and $\lVert p_k \rVert = \Delta_k$
$\qquad\qquad\qquad \Delta_{k+1} = \min(2\Delta_k, \bar{\Delta})$
$\qquad\qquad$ else
$\qquad\qquad\qquad \Delta_{k+1} = \Delta_k;$
$\qquad$ if $\rho_k > \eta$
$\qquad\qquad x_{k+1} = x_k + p_k$
$\qquad$ else
$\qquad\qquad x_{k+1} = x_k;$
end(for).

Where $p_k$ is the search direction, $\bar{\Delta}$ is the trust region's upper bound, $\Delta_0$ is the starting size of the trust region, $f$ is the cost function and $m_k$ its quadratic approximation at $x_k$:

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

$B_k$ being the Hessian.

The upper bound $\bar{\Delta}$ must be chosen according to your problem. This means that you have to have a rough idea of where the minimum might reside.