Next: Finding the root of
Up: The TrustRegion subproblem
Previous: must be positive definite.
Contents
Subsections
Theorem 2 tells us that we should be looking for solutions to
4.9 and implicitly tells us what value of we
need. Suppose that has an eigendecomposition:

(4.8) 
where is a diagonal matrix of eigenvalues
and is an
orthonormal matrix of associated eigenvectors. Then

(4.9) 
We deduce immediately
from Theorem 2 that the value of we seek must satisfy
(as only then is
positive semidefinite) ( is the least eigenvalue of
). We can compute a solution
for a given value of
using:

(4.10) 
The solution we are looking for
depends on the nonlinear inequality
. To say more we need to examine
in detail.
For convenience we define
. We have that:

(4.11) 
where
is , the component of .
Suppose the problem is defined by:
We plot
the function
in Figure 4.1. Note the
pole of
at the negatives of each eigenvalues of
. In view of theorem 2, we are only interested in
. If , the optimum lies inside the trust region
boundary. Looking at the figure, we obtain
,
for
. So, it means that if
, we have an internal optimum which can be computed
using 4.9. If
, there is a unique value of
(given in the figure and by

(4.12) 
which, used inside
4.9, give the optimal .
Figure 4.1:
A plot of
for positive
definite.

Suppose the problem is defined by:
We plot
the function
in Figure 4.2. Recall that
is defined as the least eigenvalue of . We are only
interested in values of
, that is
. For value of
, we have
NOT
positive definite. This is forbidden due to theorem 2. We can see
that for any value of , there is a corresponding value of
. Geometrically, H is indefinite, so the model function
is unbounded from below. Thus the solution lies on the
trustregion boundary. For a given , found using
4.14, we obtain the optimal using 4.9.
Figure 4.2:
A plot of
for
indefinite.

Suppose the problem is defined by:
We plot
the function
in Figure 4.3. Again,
, is forbidden due to theorem 2. If,
, there is no acceptable value of
. This difficulty can only arise when is orthogonal
to the space , of eigenvectors corresponding to the most
negative eigenvalue of . When
, then
equation 4.9 has a limiting solution , where
.
Figure 4.3:
A plot of
for
semidefinite and singular(hard case).

is positive semidefinite and singular and
therefore 4.9 has several solutions. In particular, if
is an eigenvector corresponding to , we have
, and thus:

(4.13) 
holds for any value of the
scalar . The value of can be chosen so that
. There are two roots to this
equation: and . We evaluate the model at
these two points and choose as solution
, the lowest one.
Next: Finding the root of
Up: The TrustRegion subproblem
Previous: must be positive definite.
Contents
Frank Vanden Berghen
20040419