The Trust-Region subproblem

We seek the solution $s^*$ of the minimization problem:

$$\min_{s \in \Re^n} q(x_k+s) \equiv f(x_k) + \langle g_k,s \rangle + \frac{1}{2}\langle s, H_k s\rangle$$

$$\Vert s \Vert _2 < \Delta$$ subject to

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

$$\min_{s \in \Re^n} q(s) \equiv \langle g,s \rangle + \frac{1}{2}\langle s, H s\rangle$$

$$\Vert s \Vert _2 < \Delta$$ 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 $\Vert s \Vert _2 \leq \Delta$.
Definition: The trust region $\mbox{$\cal B$}$$_k$ is the set of all points such that $$$$   $\mbox{$\cal B$}$$_k= \{ x \in \Re^n \vert \Vert x- x_k \Vert _k \leq \Delta_k \}$.
Note that we must always have at the end of the algorithm:

$$q(s^*) \leq 0$$ (4.1)

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