A multilevel algorithm for solving the trust-region subproblem

              Ph. L. Toint, D. Tomanos and M. Weber-Mendonca

                                Report 07/04

We  present a multilevel  numerical algorithm  for the  exact solution  of the
Euclidean trust-region subproblem. This particular subproblem typically arises
when  optimizing a  nonlinear (possibly  non-convex) objective  function whose
variables are  discretized continuous functions,  in which case  the different
levels  of   discretization  provide   a  natural  multilevel   context.   The
trust-region problem is considered at  the highest level (corresponding to the
finest  discretization), but  information on  the problem  curvature  at lower
levels is exploited for improved  efficiency. The algorithm is inspired by the
method of  More-Sorensen (1979), for  which two different  multilevel variants
will be analyzed. Some preliminary numerical comparisons are also presented.