The secondary Trust-Region subproblem

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

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

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