Next: Finding the root of
Up: The Trust-Region 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:
![$\displaystyle H=U^T
\Lambda U$](img572.png) |
(4.8) |
where
is a diagonal matrix of eigenvalues
and
is an
orthonormal matrix of associated eigenvectors. Then
![$\displaystyle H(\lambda)= U^T (\Lambda+\lambda I)U$](img576.png) |
(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:
![$\displaystyle s(\lambda)= - H(\lambda)^{-1} g = -U^T
(\Lambda+\lambda I)^{-1}U g$](img579.png) |
(4.10) |
The solution we are looking for
depends on the non-linear inequality
. To say more we need to examine
in detail.
For convenience we define
. We have that:
![$\displaystyle \psi(\lambda)= \Vert U^T (\Lambda+\lambda
I)^{-1}U g \Vert _2^2 ...
...a I)^{-1}U g \Vert _2^2 =
\sum_{i=1}^n \frac{\gamma_i^2}{ \lambda_i + \lambda}$](img583.png) |
(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
![$\displaystyle \Vert s(\lambda)
\Vert _2 - \Delta =0$](img596.png) |
(4.12) |
which, used inside
4.9, give the optimal
.
Figure 4.1:
A plot of
for
positive
definite.
![\begin{figure}
\centering\epsfig{figure=figures/psi1.eps, width=9cm,
height=6.5cm}
\end{figure}](img597.png) |
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
trust-region boundary. For a given
, found using
4.14, we obtain the optimal
using 4.9.
Figure 4.2:
A plot of
for
indefinite.
![\begin{figure}
\centering\epsfig{figure=figures/psi2.eps, width=9cm,
height=6.5cm}
\end{figure}](img603.png) |
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
semi-definite and singular(hard case).
![\begin{figure}
\centering\epsfig{figure=figures/psi3.eps, width=9cm,
height=6.5cm}
\end{figure}](img611.png) |
is positive semi-definite and singular and
therefore 4.9 has several solutions. In particular, if
is an eigenvector corresponding to
, we have
, and thus:
![$\displaystyle H(-\lambda_1) (s_{cri}+
\alpha u_1) = -g$](img614.png) |
(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 Trust-Region subproblem
Previous: must be positive definite.
  Contents
Frank Vanden Berghen
2004-04-19