next up previous contents
Next: An estimation of the Up: The Trust-Region subproblem Previous: The Rayleigh quotient trick   Contents

Subsections

Termination Test.

\begin{figure}
% latex2html id marker 4010
\centering\fbox{\hspace{0.2cm}\parb...
...hat{s})\leq (1-\kappa) q(s^*)\end{equation}}
} }\vspace{-0.1cm}
\end{figure}

In other words, if $ \kappa$ is small, then the reduction in $ q$ that occurs at the point $ \hat{s}$ is close to the greatest reduction that is allowed by the trust region constraint.
Proof
for any $ v$, we have the identity:

$\displaystyle q(s(\lambda)+v) =$ $\displaystyle \langle g, s(\lambda)+v\rangle + \frac{1}{2}
 \langle s(\lambda)+v , H (s(\lambda)+v) \rangle$    

( using $ H(\lambda)= H+ \lambda I$ : )


$\displaystyle =$ $\displaystyle \langle
 g, s(\lambda)+v\rangle + \frac{1}{2} \langle s(\lambda)+...
...da) (s(\lambda)+v) \rangle - \frac{1}{2}
 \lambda \Vert s(\lambda)+v \Vert _2^2$    

( using $ H(\lambda) s(\lambda)= - g $ : )


$\displaystyle =$ $\displaystyle -
 \langle H(\lambda)s(\lambda), (s(\lambda)+v) \rangle + \frac{1...
...a) (s(\lambda)+v) \rangle -
 \frac{1}{2}
 \lambda \Vert s(\lambda)+v \Vert _2^2$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \langle v,H(\lambda)v\rangle - \frac{1}{2} \langle
 s...
...lambda) s(\lambda) \rangle - \frac{1}{2} \lambda
 \Vert s(\lambda)+v \Vert _2^2$ (4.23)

If we choose $ v$ such that $ s(\lambda)+v=s^*$, we have:

$\displaystyle q(s^*)
\geq - \frac{1}{2} ( \langle s(\lambda) , H(\lambda) s(\l...
...2} (
\langle s(\lambda) , H(\lambda) s(\lambda) \rangle + \lambda
\Delta^2 ) $

$\displaystyle \Rightarrow \quad - \frac{1}{2} ( \langle
 s(\lambda) , H(\lambda) s(\lambda) \rangle + \lambda \Delta^2 )
 \leq q(s^*)$ (4.24)

From 4.27, using the 2 hypothesis:

$\displaystyle q(s(\lambda)+v) =$ $\displaystyle \frac{1}{2} \langle v,H(\lambda)v\rangle - \frac{1}{2} \langle
 s...
...lambda) s(\lambda) \rangle - \frac{1}{2} \lambda
 \Vert s(\lambda)+v \Vert _2^2$    
$\displaystyle =$ $\displaystyle \frac{1}{2} \langle v,H(\lambda)v\rangle - \frac{1}{2} \langle
 s(\lambda) , H(\lambda) s(\lambda) \rangle - \frac{1}{2}
 \lambda \Delta^2$    

( Using Equation 4.25: )


$\displaystyle \leq$ $\displaystyle \frac{1}{2}
 \; \kappa \; ( \langle s(\lambda), H(\lambda) s(\lam...
...gle s(\lambda) , H(\lambda)
 s(\lambda) \rangle - \frac{1}{2}
 \lambda \Delta^2$    
$\displaystyle \leq$ $\displaystyle - \frac{1}{2} \; (1- \kappa )\; ( \langle s(\lambda),
 H(\lambda) s(\lambda) \rangle + \lambda \Delta^2 )$ (4.25)

Combining 4.28 and 4.29, we obtain finally 4.26.

$ s(\lambda )$ is near the boundary of the trust region: normal case

Lemma

\begin{figure}
\centering\fbox{\hspace{0.2cm}\parbox[t][2.2cm][b]{15.7cm}{
{...
...)< (1-\kappa_{easy}^2)
q(s^*)\end{equation}
} }\vspace{-0.1cm}
\end{figure}

From the hypothesis:
$\displaystyle \vert \Vert s(\lambda)\Vert _2 - \Delta \vert$ $\displaystyle \leq$ $\displaystyle \kappa_{easy} \Delta
\nonumber$  
$\displaystyle \Vert s(\lambda)\Vert _2$ $\displaystyle \geq$ $\displaystyle (1-\kappa_{easy}) \Delta$ (4.26)

Combining 4.31 and 4.27 when $ v=0$ reveals that:
$\displaystyle q(s(\lambda))$ $\displaystyle =$ $\displaystyle - \frac{1}{2}( \langle s(\lambda) , H(\lambda)
s(\lambda) \rangle + \lambda \Vert s(\lambda) \Vert _2^2 )$  
  $\displaystyle \leq$ $\displaystyle - \frac{1}{2}( \langle s(\lambda) , H(\lambda) s(\lambda)
\rangle + \lambda (1-\kappa_{easy})^2 \Delta^2 )$  
  $\displaystyle \leq$ $\displaystyle - \frac{1}{2} (1-\kappa_{easy})^2 ( \langle s(\lambda) ,
H(\lambda) s(\lambda) \rangle + \lambda \Delta^2 )$ (4.27)

The required inequality 4.30 is immediate from 4.28 and 4.32.
We will use this lemma with $ \kappa_{easy}=0.1$.

$ s(\lambda )$ is inside the trust region: hard case

We will choose $ \hat{s}$ as (see paragraph containing Equation 4.15 for the meaning of $ \alpha^*$ and $ u_1$):

$\displaystyle \hat{s}= s(\lambda)+ \alpha^* u_1$ (4.28)

Thus, the condition for ending the trust region calculation simplifies to the inequality:

$\displaystyle \alpha^2 \langle u, H(\lambda)u \rangle < \kappa_{hard}
 (s(\lambda)^T H(\lambda) s(\lambda) + \lambda \Delta^2)$ (4.29)

We will choose $ \kappa_{hard}=0.02$.
next up previous contents
Next: An estimation of the Up: The Trust-Region subproblem Previous: The Rayleigh quotient trick   Contents
Frank Vanden Berghen 2004-04-19