Next: Generating . Up: Unconstrained Optimization Previous: An estimation of the   Contents

# The secondary Trust-Region subproblem

The material of this chapter is based on the following reference: [Pow00].
We seek an approximation to the solution , of the maximization problem:

 subject to

The following maximization problem is equivalent (after a translation) and will be discussed in the chapter:

 (5.1) subject to

We will indifferently use the term, polynomial, quadratic or model. The trust region'' is defined by the set of all points which respect the constraint .
Further, the shape of the trust region allows to be replaced by , it's thus equivalent to consider the computation

 (5.2) subject to

Now, if and are the values that maximize and , respectively, subject to , then may be an adequate solution of the problem 5.1, if it is the choice between and that gives the largest value of the objective function of the problem. Indeed, for every feasible , including the exact solution of the present computation, we find the elementary bound
 (5.3)

It follows that the proposed choice of gives a value of that is, at least, half of the optimal value. Now, is the vector , while is an eigenvector of an eigenvalue of of largest modulus, which would be too expensive to compute. We will now discuss how to generate . We will use a method inspired by the power method for obtaining large eigenvalues.
Because is large only if is substantial, the technique begins by finding a column of , say, that has the greatest Euclidean norm. Hence letting be the columns of the symmetric matrix , we deduce the bound
 (5.4) (5.5)

Where is the spectral radius of . It may be disastrous, however to set to a multiple of , because is zero in the case:

 (5.6)

Therefore, the algorithm picks from the two dimensional linear subspace of that is spanned by and . Specifically, has the form , where the ratio is computed to maximize the expression

 (5.7)

which determines the direction of . Then the length of is defined by , the sign of , being unimportant.

Subsections

Next: Generating . Up: Unconstrained Optimization Previous: An estimation of the   Contents
Frank Vanden Berghen 2004-04-19