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:

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

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

where

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

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

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