next up previous contents
Next: How to pick inside Up: The Trust-Region subproblem Previous: Finding the root of   Contents

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: $ \displaystyle \lambda= \frac{\Vert g\Vert}{\Delta}$
  3. Try to factorize $ H(\lambda)=L L^T$ (if not already done).
  4. return to step 3.

next up previous contents
Next: How to pick inside Up: The Trust-Region subproblem Previous: Finding the root of   Contents
Frank Vanden Berghen 2004-04-19