next up previous contents
Next: must be positive definite. Up: Unconstrained Optimization Previous: The Lagrange Interpolation inside   Contents


The Trust-Region subproblem

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

$\displaystyle \min_{s \in \Re^n} q(x_k+s) \equiv f(x_k)$ $\displaystyle + \langle g_k,s \rangle +
 \frac{1}{2}\langle s, H_k s\rangle$    
subject to $\displaystyle \Vert s \Vert _2 < \Delta$    

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:

$\displaystyle \min_{s \in \Re^n} q(s) \equiv \langle g,s \rangle$ $\displaystyle +
 \frac{1}{2}\langle s, H s\rangle$    
subject to $\displaystyle \Vert s \Vert _2 < \Delta$    

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 $ \displaystyle$   $ \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:

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

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


Subsections
next up previous contents
Next: must be positive definite. Up: Unconstrained Optimization Previous: The Lagrange Interpolation inside   Contents
Frank Vanden Berghen 2004-04-19