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 such that and . What happens if (or equivalently )? The Cholesky factorization succeeds and so we can apply 4.21. We get a new value for but we must be careful because this new value can be in the forbidden region .
If we are in the hard case, it's never possible to get (or equivalently ), 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 and respectively a lower and upper bound on the lowest eigenvalue of .
2. Choose . We will choose:
3. Try to factorize (if not already done).
• Success:
1. solve
2. Compute :
• :
We must be careful: the next value of can be in the forbidden region. We may also have interior convergence: Check :
• : The algorithm is finished. We have found the solution (which is inside the trust region).
• : We are maybe in the hard case. Use the methods described in the paragraph containing the Equation 4.15 to find . Check for termination for the hard case.
• :
3. Check for termination for the normal case: is on the boundary of the trust region.
4. Solve
5. Compute
6. Check : Try to factorize
• Success: replace by
• Failure:
The Newton's method, just failed to choose a correct . Use the alternative'' algorithm: pick inside (see Section 4.5 ).
• Failure: Improve using Rayleigh's quotient trick (see Section 4.8 ). Use the alternative'' algorithm: pick inside (see section 4.5 ).