Title

MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization

Abstract

We study the combination of proximal gradient descent with multigrid for solving a class of possibly nonsmooth convex optimization problems. We propose a multigrid proximal gradient method called MGProx, which accelerates the proximal gradient method by multigrid, based on utilizing hierarchical information of the optimization problem. MGProx applies a newly introduced adaptive restriction operator to simplify the Minkowski sum of subdifferentials of the nondifferentiable objective function across different levels. We provide a theoretical characterization of MGProx. First we show that variables at all levels exhibit a fixed-point property at convergence. Next, we show that the coarse correction is a descent direction for the fine variable in the general nonsmooth case. Lastly, under some mild assumptions we provide the O(1/k²) convergence rate for the algorithm. In the numerical experiments, we show that MGProx has a significantly faster convergence speed than proximal gradient descent and proximal gradient descent with Nesterov’s acceleration on nonsmooth convex optimization problems such as the Elastic Obstacle Problem. If time permits we will talk about the extension to primal-dual algorithm, ADMM and also to non-convex non-proximable problems.

Joint work with Hans De Sterck (U. Waterloo) and Stephen Vavasis (U. Waterloo), arXiv 2302.04077