Next: About the CONDOR algorithm.
Up: An introduction to the
Previous: A simple trust-region algorithm.
  Contents
Defnition: The trust region
![$ \mbox{$\cal B$}$](img217.png)
is the set of all points
such that
![$\displaystyle \mbox{$\cal B$}$](img218.png) ![$\displaystyle _k= \{ x \in \Re^n \vert \Vert x- x_k \Vert _k \leq \Delta_k
\}$](img219.png) |
(2.18) |
The simple algorithm described in the Section 2.2 can be
generalized as follows:
- Initialization An initial point
and an initial
trust region radius
are given. The constants
,
,
and
are also given and satisfy:
and ![$\displaystyle 0 < \gamma_1 \leq
\gamma_2 <1$](img227.png) |
(2.19) |
Compute
and set
- Model definition Choose the norm
and
define a model
in
![$ \mbox{$\cal B$}$](img217.png)
- Step computation Compute a step
that
''sufficiently reduces the model''
and such that
![$ \mbox{$\cal B$}$](img217.png)
- Acceptance of the trial point. Compute
and define:
![$\displaystyle r_k
=\frac{f(x_k)-f(x_k+s_k)}{m_k(x_k)-m_k(x_k+s_k)}$](img234.png) |
(2.20) |
If
, then define
; otherwise define
.
- 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} \\ $](img238.png) |
(2.21) |
Increment
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: About the CONDOR algorithm.
Up: An introduction to the
Previous: A simple trust-region algorithm.
  Contents
Frank Vanden Berghen
2004-04-19