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 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 on the fine grid. A new theoretical complexity result is also proved for single- as well as multilevel 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.
Technical Report TR04/06 Department of Mathematics University of Namur, 61, rue de Bruxelles, B-5000 Namur (Belgium)