next up previous contents
Next: Termination Test. Up: The Trust-Region subproblem Previous: How to find a   Contents


The Rayleigh quotient trick

If $ H$ is symmetric and the vector $ p\neq 0$, then the scalar

$\displaystyle \frac{\langle p, H p\rangle}{\langle p,p\rangle} $

is known as the Rayleigh quotient of p. The Rayleigh quotient is important because it has the following property:

$\displaystyle \lambda_{min}[H] \leq \frac{\langle p, H p\rangle}{\langle
 p,p\rangle} \leq \lambda_{max}[H]$ (4.21)

During the Cholesky factorization of $ H(\lambda)$, we have encountered a negative pivot at the $ k^{\text{th}}$ stage of the decomposition for some $ k\leq n$. The factorization has thus failed ($ H$ is indefinite). It is then possible to add $ \delta=
\sum_{j=1}^{k-1} l_{kj}^2- h_{kk}(\lambda) \geq 0$ to the $ k^{\text{th}}$ diagonal of $ H(\lambda)$ so that the leading $ k$ by $ k$ submatrix of

$\displaystyle H(\lambda)+ \delta e_k e_k^T $

is singular. It's also easy to find a vector $ v$ for which

$\displaystyle H(\lambda+ \delta e_k e_k^T)v=0$ (4.22)

using the Cholesky factors accumulated up to step $ k$. Setting $ v_j=0$ for $ j>k, v_k=1$, and back-solving:

$\displaystyle v_j=- \frac{\sum_{i=j+1}^k
l_{ij} v_i}{l_{jj}} \text{ for } j=k-1, \ldots, 1 $

gives the required vector. We then obtain a lower bound on $ -\lambda_1$ by forming the inner product of 4.24 with $ v$, using the identity $ \langle e_k,v\rangle=v_k=1$ and recalling that the Rayleigh quotient is greater then $ \lambda_{min}=\lambda_1$, we can write:

$\displaystyle 0= \frac{\langle v, (H+\lambda I) v\rangle}{\langle v,v\rangle}
...
...le v,v\rangle} \geq
\lambda + \lambda_1 + \frac{\delta}{ \Vert v\Vert _2^2 }
$

This implies the bound on $ \lambda_1$:

$\displaystyle \lambda + \frac{\delta}{ \Vert v\Vert _2^2 } \leq - \lambda_1 $

In the algorithm, we set $ \displaystyle \lambda_L = \max [ \lambda_L,
\lambda + \frac{\delta}{ \Vert v\Vert _2^2 } ]$
next up previous contents
Next: Termination Test. Up: The Trust-Region subproblem Previous: How to find a   Contents
Frank Vanden Berghen 2004-04-19