The basic trust-region algorithm (BTR).

Defnition: The trust region $\mbox{$\cal B$}$$_k$ is the set of all points such that

$$\mbox{$\cal B$} _k= \{ x \in \Re^n \vert \Vert x- x_k \Vert _k \leq \Delta_k \}$$ (2.18)

The simple algorithm described in the Section 2.2 can be generalized as follows:

1. Initialization An initial point $x_0$ and an initial trust region radius $\Delta_0$ are given. The constants $\eta_1$, $\eta_2$, $\gamma_1$ and $\gamma_2$ are also given and satisfy:

   $$0 < \eta_1 \leq \eta_2 <1 0 < \gamma_1 \leq \gamma_2 <1$$ (2.19)

   
   
   Compute $f(x_0)$ and set $k=0$
2. Model definition Choose the norm $\Vert \cdot \Vert _k$ and define a model $m_k$ in $\mbox{$\cal B$}$$_k$
3. Step computation Compute a step $s_k$ that ''sufficiently reduces the model'' $m_k$ and such that $x_k+s_k \in$   $\mbox{$\cal B$}$$_k$
4. Acceptance of the trial point. Compute $f(x_k+s_k)$ and define:

   $$r_k =\frac{f(x_k)-f(x_k+s_k)}{m_k(x_k)-m_k(x_k+s_k)}$$ (2.20)

   
   
   If $r_k \geq \eta_1$, then define $x_{k+1}=x_k+s_k$ ; otherwise define $x_{k+1}=x_k$.
5. Trust region radius update. Set

   $$\Delta_{k+1} \in \begin{cases}[ \Delta_k, \infty) & \text{if } ... ...amma_1 \Delta_k, \gamma_2 \Delta_k) & \text{if } r_k < \eta_1. \end{cases} \\$$ (2.21)

   
   
   Increment $k$ by 1 and go to step 2.

Under some very weak assumptions, it can be proven that this algorithm is globally convergent to a local optimum [CGT00a]. The proof will be skipped.