Next: Explanation of the Hard Up: The Trust-Region subproblem Previous: The Trust-Region subproblem   Contents

must be positive definite.

The solution we are seeking lies either interior to the trust region ( ) or on the boundary.
If it lies on the interior, the trust region may as well not have been there and therefore is the unconstrained minimizer of . We have seen in Equation 2.4 () how to find it. We have seen in Equation 2.6 that

 must be definite positive (4.2)

in order to be able to apply 2.4.
If we found a value of using 2.4 which lies outside the trust region, it means that lies on the trust region boundary. Let's take a closer look to this case:
Theorem 1

First, we rewrite the constraints as . Now, we introduce a Lagrange multiplier for the constraint and use first-order optimality conditions (see Annexe, section 13.3 ). This gives:

 (4.3)

Using first part of Equation 13.22,we have

 (4.4)

which is 4.3.
We will now proof that must be positive (semi)definite.
Suppose is a feasible point ( ), we obtain:

 (4.5)

Using the secant equation (see Annexes, Section 13.4), , we can rewrite 4.5 into . This and the restriction that implies that:

Combining 4.6 and 4.7

Let's define a line as a function of the scalar . This line intersect the constraints for two values of : and at which . So , and therefore, using 4.8, we have that

Finally, as we are assuming that is a global minimizer, we must have that , and thus that , which is the same as saying that is positive semidefinite.
If is positive definite, then for any , and therefore 4.8 shows that whenever is feasible. Thus is the unique global minimizer.
Using 4.2 (which is concerned about an interior minimizer) and the previous paragraph (which is concerned about a minimizer on the boundary of the trust region), we can state:
Theorem 2:

The justification of is simply the complementarity condition (see Section 13.3 for explanation, Equation 13.22).
The parameter is said to regularized'' or modify'' the model such that the modified model is convex and so that its minimizer lies on or within the trust region boundary.

Next: Explanation of the Hard Up: The Trust-Region subproblem Previous: The Trust-Region subproblem   Contents
Frank Vanden Berghen 2004-04-19