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:

$$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

$$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:

$$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:

$$\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:

$$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

$$\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.

Non-Convex example.

Suppose the problem is defined by:

$$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.

The hard case.

Suppose the problem is defined by:

$$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 $$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).

$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:

$$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.