Solving the trust-region subproblem using the Lanczos method

       N. Gould      S. Lucidi    M. Roma   Ph.L. Toint

                     Report 97/11      10 June 1997

The approximate minimization  of  a quadratic  function within an  ellipsoidal
trust region is   an   important subproblem  for  many  nonlinear  programming
methods. When the number of variables is large,  the most widely-used strategy
is to trace the  path of conjugate  gradient iterates either to convergence or
until it reaches the trust-region boundary. In this paper, we investigate ways
of continuing the  process once the boundary has  been encountered. The key is
to observe that the trust-region problem within the currently generated Krylov
subspace  has   very special structure  which   enables it to   be solved very
efficiently.  We compare the new strategy with existing methods. The resulting
software package   is available  as  HSL_F05  within the   Harwell  Subroutine
Library.