next up previous contents
Next: About the CONDOR algorithm. Up: An introduction to the Previous: A simple trust-region algorithm.   Contents

The basic trust-region algorithm (BTR).

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

$\displaystyle \mbox{$\cal B$}$$\displaystyle _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:

    $\displaystyle 0 < \eta_1 \leq \eta_2 <1$    and $\displaystyle 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:

    $\displaystyle 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

    $\displaystyle \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.
next up previous contents
Next: About the CONDOR algorithm. Up: An introduction to the Previous: A simple trust-region algorithm.   Contents
Frank Vanden Berghen 2004-04-19