next up previous contents
Next: The basic trust-region algorithm Up: An introduction to the Previous: Trust Region and Line-search   Contents


A simple trust-region algorithm.

In all trust-region algorithms, we always choose $ \alpha_k=1$. The length of the steps will be adjusted using $ \Delta$, the trust region radius.
Recall that $ \mbox{$\cal Q$}$$ _k(\delta)= f(x_k)+ <g_k,\delta>+
\frac{1}{2}<\delta, B_k \delta>$ is the quadratical approximation of $ \mbox{$\cal F$}$$ (x)$ around $ x_k$.
A simple trust-region algorithm is:
  1. solve $ B_k \delta_k=-g_k$ subject to $ \Vert
\delta_k \Vert < \Delta_k $.
  2. Compute the ``degree of agreement'' $ r_k$ between $ \mbox{$\cal F$}$ and $ \mbox{$\cal Q$}$:

    $\displaystyle r_k=\frac{f(x_k)-f(x_k+\delta_k)}{\mbox{$\cal Q$}_k(0)-\mbox{$\cal Q$}_k(\delta_k)}$ (2.15)

  3. update $ x_k$ and $ \Delta_k $ :

    \begin{displaymath}\begin{array}{\vert l\vert l\vert l\vert} \hline
 \displaysty...
...\displaystyle \Delta_{k+1}=2 \Delta_k \\
 \hline
 \end{array}\end{displaymath} (2.16)

  4. Increment $ k$. Stop if $ g_k\approx 0$ otherwise, go to step 1.

The main idea in this update is: only increase $ \Delta_k $ when the local approximator $ \mbox{$\cal Q$}$ reflects well the real function $ \mbox{$\cal F$}$.
At each iteration of the algorithm, we need to have $ B_k$ and $ g_k$ to compute $ \delta_k$.
There are different ways for obtaining $ g_k$: There are different ways for obtaining $ B_k$. Many are unpractical. Here are some reasonable ones:
next up previous contents
Next: The basic trust-region algorithm Up: An introduction to the Previous: Trust Region and Line-search   Contents
Frank Vanden Berghen 2004-04-19