Next: Termination Test.
Up: The Trust-Region subproblem
Previous: How to find a
  Contents
The Rayleigh quotient trick
If
is symmetric and the vector
, then the scalar
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]$](img683.png) |
(4.21) |
During the Cholesky factorization of
, we have
encountered a negative pivot at the
stage of the
decomposition for some
. The factorization has thus
failed (
is indefinite). It is then possible to add
to the
diagonal of
so that the leading
by
submatrix of
is
singular. It's also easy to find a vector
for which
 |
(4.22) |
using the
Cholesky factors accumulated up to step
. Setting
for
, and back-solving:
gives the
required vector. We then obtain a lower bound on
by
forming the inner product of 4.24 with
, using the
identity
and recalling that the
Rayleigh quotient is greater then
, we
can write:
This implies the bound on
:
In the
algorithm, we set
Next: Termination Test.
Up: The Trust-Region subproblem
Previous: How to find a
  Contents
Frank Vanden Berghen
2004-04-19