next up previous contents
Next: Starting and safe-guarding Newton's Up: The Trust-Region subproblem Previous: Explanation of the Hard   Contents

Finding the root of $ \Vert s(\lambda) \Vert _2 - \Delta =0$.

We will apply the 1D-optimization algorithm called ``1D Newton's search'' (see Annexes, Section 13.5) to the secular equation:

$\displaystyle \phi(\lambda)=\frac{1}{\Vert
 s(\lambda)\Vert _2}-\frac{1}{\Delta}$ (4.14)

We use the secular equation instead of $ \psi(\lambda) - \Delta^2=
\Vert s(\lambda) \Vert _2^2 - \Delta^2 =0$ inside the ``1D Newton's search'' because this last function is better behaved than $ \psi (\lambda )$. In particular $ \phi(\lambda)$ is strictly increasing when $ \lambda>\lambda_1$, and concave. It's first derivative is:

$\displaystyle \phi'(\lambda)= - \frac{ \langle s(\lambda) ,
 \nabla_\lambda s(\lambda)\rangle }{ \Vert s(\lambda)\Vert _2^3}$ (4.15)

where

$\displaystyle \nabla_\lambda s(\lambda) = -
 H(\lambda)^{-1} s(\lambda)$ (4.16)

The proof of these properties will be skipped.
In order to apply the ``1D Newton's search'':

$\displaystyle \lambda_{k+1}=
 \lambda_k- \frac{\phi(\lambda)}{\phi'(\lambda)}$ (4.17)

we need to evaluate the function $ \phi(\lambda)$ and $ \phi'(\lambda)$. The value of $ \phi(\lambda)$ can be obtained by solving the Equation 4.9 to obtain $ s(\lambda )$. The value of $ \phi'(\lambda)$ is available from 4.17 once $ \nabla_\lambda s(\lambda) $ has been found using 4.18. Thus both values may be found by solving linear systems involving $ H(\lambda)$. Fortunately, in the range of interest, $ H(\lambda)$ is definite positive, and thus, we may use its Cholesky factors $ H(\lambda)= L(\lambda) L(\lambda)^T$ (see Annexes, Section 13.7 for notes about Cholesky decomposition ). Notice that we do not actually need tho find $ \nabla_\lambda s(\lambda) $, but merely the numerator $ \langle s(\lambda), \nabla_\lambda
s(\lambda)\rangle = - \langle s(\lambda), H(\lambda)^{-1}
s(\lambda)\rangle $ of 4.17. The simple relationship

$\displaystyle \langle s(\lambda), H(\lambda)^{-1} s(\lambda)\rangle = \langle
 ...
...gle = \langle L^{-1}
 s(\lambda), L^{-1} s(\lambda)\rangle = \Vert\omega\Vert^2$ (4.18)

explains why we compute $ \omega$ in step 3 of the following algorithm. Step 4 of the algorithm follows directly from 4.17 and 4.19. Newton's method to solve $ \phi(\lambda)=0$:
  1. find a value of $ \lambda $ such that $ \lambda>\lambda_1$ and $ \lambda<\lambda^*$.
  2. factorize $ H(\lambda)=L L^T$
  3. solve $ L L^T s= -g$
  4. Solve $ L \omega= s$
  5. Replace $ \lambda $ by $\displaystyle \lambda+(\frac{\Vert s(\lambda)\Vert _2-\Delta}{\Delta})(\frac{\Vert s(\lambda)\Vert _2^2}{\Vert\omega\Vert _2^2})$ (4.19)

  6. If stopping criteria are not met, go to step 2.
Once the algorithm has reached point 2. It will always generate values of $ \lambda>\lambda_1$. Therefore, the Cholesky decomposition will never fails and the algorithm will finally find $ \lambda^*$. We skip the proof of this property.

next up previous contents
Next: Starting and safe-guarding Newton's Up: The Trust-Region subproblem Previous: Explanation of the Hard   Contents
Frank Vanden Berghen 2004-04-19