The Trust-Region subproblem

subject to |

The following minimization problem is equivalent to the previous one after a translation of the polynomial in the direction (see Section 3.4.6 about polynomial translation). Thus, this problem will be discussed in this chapter:

subject to |

We will indifferently use the terms, polynomial, quadratic or model. The ``trust region'' is defined by the set of all the points which respects the constraint .

Note that we must always have at the end of the algorithm:

The material of this chapter is based on the following references: [CGT00c,MS83].

- must be positive definite.
- Explanation of the Hard case.

- Finding the root of .
- Starting and safe-guarding Newton's method
- How to pick inside ?
- Initial values of and
- How to find a good approximation of : LINPACK METHOD
- The Rayleigh quotient trick
- Termination Test.

- An estimation of the slope of at the origin.