A Line Search Multigrid Method for Large-Scale Convex Optimization

Abstract. We present a line search multigrid method based on Nash’s MG/OPT multilevel optimization approach for solving discretized versions of convex infinite dimensional optimization problems. Global convergence is proved under fairly minimal requirements on the minimization method used at all grid levels. In particular, our convergence proof does not require that these minimization, or so-called “smoothing ” steps, which we interpret in the context of optimization, be taken at each grid level in contrast with multigrid algorithms for PDEs, which fail to converge without such steps. Preliminary numerical experiments show that our method is promising