Starting and safe-guarding Newton's method

In step 1 of Newton's method, we need to find a value of $\lambda$ such that $\lambda>\lambda_1$ and $\lambda<\lambda^*$. What happens if $\lambda>\lambda^*$ (or equivalently $\Vert s(\lambda)\Vert < \Vert\Delta\Vert$)? The Cholesky factorization succeeds and so we can apply 4.21. We get a new value for $\lambda$ but we must be careful because this new value can be in the forbidden region $\lambda< \lambda_1$.
If we are in the hard case, it's never possible to get $\lambda<\lambda_*$ (or equivalently $\Vert s(\lambda)\Vert>\Vert\Delta\Vert$), therefore we will never reach point 2 of the Newton's method.
In the two cases described in the two previous paragraphs, the Newton's algorithm fails. We will now describe a modified Newton's algorithm which prevents these failures:

1. Compute $\lambda _L$ and $\lambda _U$ respectively a lower and upper bound on the lowest eigenvalue $\lambda_1$ of $H$.
2. Choose $\lambda \in [\lambda_L \lambda_U]$. We will choose: $$\lambda= \frac{\Vert g\Vert}{\Delta}$$
3. Try to factorize $H(\lambda)=L L^T$ (if not already done).
   • Success:
     1. solve $L L^T s= -g$
     2. Compute $\Vert s \Vert$:
        • $\Vert s \Vert < \Delta$ : $\lambda_U := min ( \lambda_U, \lambda )$
          We must be careful: the next value of $\lambda$ can be in the forbidden $\lambda< \lambda_1$ region. We may also have interior convergence: Check $\lambda$:
          • $\lambda=0$: The algorithm is finished. We have found the solution $s^*$ (which is inside the trust region).
          • $\lambda \neq 0$: We are maybe in the hard case. Use the methods described in the paragraph containing the Equation 4.15 to find $\Vert s+\alpha u_1\Vert _2= \Vert \delta \Vert _2$. Check for termination for the hard case.
        • $\Vert s \Vert > \Delta$ : $\lambda_L := max ( \lambda_L, \lambda)$
          
     3. Check for termination for the normal case: $s^*$ is on the boundary of the trust region.
     4. Solve $L \omega= s$
     5. Compute $$\lambda_{new}= \lambda+(\frac{\Vert s(\lambda)\Vert _2-\Delta}{\Delta})(\frac{\Vert s(\lambda)\Vert _2^2}{\Vert\omega\Vert _2^2})$$
     6. Check $\lambda_{new}$: Try to factorize $H(\lambda_{new} )= L L^T$
        • Success: replace $\lambda$ by $\lambda_{new}$
        • Failure: $\lambda_L = max( \lambda_L, \lambda_{new})$
          The Newton's method, just failed to choose a correct $\lambda$. Use the ``alternative'' algorithm: pick $\lambda$ inside $[\lambda _L \lambda _U]$ (see Section 4.5 ).
   • Failure: Improve $\lambda _L$ using Rayleigh's quotient trick (see Section 4.8 ). Use the ``alternative'' algorithm: pick $\lambda$ inside $[\lambda _L \lambda _U]$ (see section 4.5 ).
4. return to step 3.