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.