next up previous contents
Next: Finding the root of Up: The Trust-Region subproblem Previous: must be positive definite.   Contents

Subsections

Explanation of the Hard case.

Theorem 2 tells us that we should be looking for solutions to 4.9 and implicitly tells us what value of $ \lambda $ we need. Suppose that $ H$ has an eigendecomposition:

$\displaystyle H=U^T
 \Lambda U$ (4.8)

where $ \Lambda$ is a diagonal matrix of eigenvalues $ \lambda_1< \lambda_2< \ldots <\lambda_n $ and $ U$ is an orthonormal matrix of associated eigenvectors. Then

$\displaystyle H(\lambda)= U^T (\Lambda+\lambda I)U$ (4.9)

We deduce immediately from Theorem 2 that the value of $ \lambda $ we seek must satisfy $ \lambda^* > \min [ 0, -\lambda_1 ]$ (as only then is $ H(\lambda)$ positive semidefinite) ($ \lambda_1$ is the least eigenvalue of $ H$). We can compute a solution $ s(\lambda )$ for a given value of $ \lambda $ using:

$\displaystyle s(\lambda)= - H(\lambda)^{-1} g = -U^T
 (\Lambda+\lambda I)^{-1}U g$ (4.10)

The solution we are looking for depends on the non-linear inequality $ \Vert s(\lambda) \Vert _2 < \Delta
$. To say more we need to examine $ \Vert s(\lambda) \Vert _2$ in detail. For convenience we define $ \psi(\lambda) \equiv \Vert s(\lambda)
\Vert _2^2$. 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}$ (4.11)

where $ \gamma_i$ is $ [Ug]_i$, the $ i^{th}$ component of $ U
g$.

Convex example.

Suppose the problem is defined by:

$\displaystyle g= \begin{pmatrix}1 \\  1 \\
1\\  1 \end{pmatrix}, H= \begin{p...
...0 & 0 & 0 \\  0 & 2 &
0 & 0 \\  0 & 0 & 3 & 0 \\  0 & 0 & 0 & 4 \end{pmatrix} $

We plot the function $ \psi (\lambda )$ in Figure 4.1. Note the pole of $ \psi (\lambda )$ at the negatives of each eigenvalues of $ H$. In view of theorem 2, we are only interested in $ \lambda >
0$. If $ \lambda=0$, the optimum lies inside the trust region boundary. Looking at the figure, we obtain $ \lambda=\lambda^*=0$, for $ \psi(\lambda)= \Delta^2 > 1.5$. So, it means that if $ \Delta^2>1.5$, we have an internal optimum which can be computed using 4.9. If $ \Delta^2<1.5$, there is a unique value of $ \lambda= \lambda^*$ (given in the figure and by

$\displaystyle \Vert s(\lambda)
 \Vert _2 - \Delta =0$ (4.12)

which, used inside 4.9, give the optimal $ s^*$.

Figure 4.1: A plot of $ \psi (\lambda )$ for $ H$ positive definite.
\begin{figure}
\centering\epsfig{figure=figures/psi1.eps, width=9cm,
height=6.5cm}
\end{figure}

Non-Convex example.

Suppose the problem is defined by:

$\displaystyle g= \begin{pmatrix}1 \\  1 \\
1\\  1 \end{pmatrix}, H= \begin{p...
... & 0 & 0 \\  0 & -1
& 0 & 0 \\  0 & 0 & 0 & 0 \\  0 & 0 & 0 & 1 \end{pmatrix} $

We plot the function $ \psi (\lambda )$ in Figure 4.2. Recall that $ \lambda_1$ is defined as the least eigenvalue of $ H$. We are only interested in values of $ \lambda > -\lambda_1$, that is $ \lambda >
2$. For value of $ \lambda< \lambda_1 $, we have $ H(\lambda)$ NOT positive definite. This is forbidden due to theorem 2. We can see that for any value of $ \Delta$, there is a corresponding value of $ \lambda >
2$. Geometrically, H is indefinite, so the model function is unbounded from below. Thus the solution lies on the trust-region boundary. For a given $ \lambda^*$, found using 4.14, we obtain the optimal $ s^*$ using 4.9.

Figure 4.2: A plot of $ \psi (\lambda )$ for $ H$ indefinite.
\begin{figure}
\centering\epsfig{figure=figures/psi2.eps, width=9cm,
height=6.5cm}
\end{figure}

The hard case.

Suppose the problem is defined by:

$\displaystyle g= \begin{pmatrix}0 \\  1 \\
1\\  1 \end{pmatrix}, H= \begin{p...
... & 0 & 0 \\  0 & -1
& 0 & 0 \\  0 & 0 & 0 & 0 \\  0 & 0 & 0 & 1 \end{pmatrix} $

We plot the function $ \psi (\lambda )$ in Figure 4.3. Again, $ \lambda< 2$, is forbidden due to theorem 2. If, $ \Delta >
\Delta_{critical} \approx 1.2$, there is no acceptable value of $ \lambda $. This difficulty can only arise when $ g$ is orthogonal to the space $ \cal E_1$, of eigenvectors corresponding to the most negative eigenvalue of $ H$. When $ \Delta=\Delta_{cri}$, then equation 4.9 has a limiting solution $ s_{cri}$, where $ \displaystyle s_{cri}=\lim_{\lambda
\rightarrow \lambda_1} s(\lambda)$.

Figure 4.3: A plot of $ \psi (\lambda )$ for $ H$ semi-definite and singular(hard case).
\begin{figure}
\centering\epsfig{figure=figures/psi3.eps, width=9cm,
height=6.5cm}
\end{figure}

$ H(\lambda_1)$ is positive semi-definite and singular and therefore 4.9 has several solutions. In particular, if $ u_1$ is an eigenvector corresponding to $ \lambda_1$, we have $ H(-\lambda_1) u_1=0$, and thus:

$\displaystyle H(-\lambda_1) (s_{cri}+
 \alpha u_1) = -g$ (4.13)

holds for any value of the scalar $ \alpha $. The value of $ \alpha $ can be chosen so that $ \Vert
s_{cri}+ \alpha u_1 \Vert _2= \Delta$ . There are two roots to this equation: $ \alpha_1$ and $ \alpha_2$. We evaluate the model at these two points and choose as solution $ s^* = s_{cri}+ \alpha^*
u_1$, the lowest one.
next up previous contents
Next: Finding the root of Up: The Trust-Region subproblem Previous: must be positive definite.   Contents
Frank Vanden Berghen 2004-04-19