Termination Test.

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:

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

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

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

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

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

$$= \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:

$$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 )$$

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

$$q(s(\lambda)+v) = \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$$

$$= \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: )

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

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

From the hypothesis:

$$\vert \Vert s(\lambda)\Vert _2 - \Delta \vert \leq \kappa_{easy} \Delta \nonumber$$

$$\Vert s(\lambda)\Vert _2 \geq (1-\kappa_{easy}) \Delta$$ (4.26)

Combining 4.31 and 4.27 when $v=0$ reveals that:

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

$$\leq - \frac{1}{2}( \langle s(\lambda) , H(\lambda) s(\lambda) \rangle + \lambda (1-\kappa_{easy})^2 \Delta^2 )$$

$$\leq - \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$):

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

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

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