Recursive Trust-Region Methods for
               Multiscale Nonlinear Optimization (Part I):
                    Global Convergence and Complexity

                  S. Gratton, A. Sartenaer, Ph. L. Toint
                                Report 04/06

A  class  of  trust-region  methods  is presented  for  solving  unconstrained
nonlinear and possibly nonconvex discretized optimization problems, like those
arising in systems governed by partial differential equations.  The algorithms
in this class  make use of the  discretization level as a mean  of speeding up
the  computation  of  the  step.  This  use  is  recursive,  leading  to  true
multiscale/multilevel optimization methods reminiscent of multigrid methods in
linear  algebra and  the  solution of  partial-differential equations.  Global
convergence  of the recursive  algorithm is  proved to  first-order stationary
points.  A  new theoretical  complexity result is  also proved for  single- as
well as multiscale  trust-region algorithms, that gives a  bound on the number
of iterations  that are necessary to reduce  the norm of the  gradient below a
given threshold.