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


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/k2) 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


Andersen Ang is a lecturer (UK system, equivalent to assistant professor in US) in the ECS at the University of Southampton, UK. Previously, he is a Fields postdoctoral fellow in the Department of Combinatorics and Optimization at the University of Waterloo, Canada, where his advisors are Stephen Vavasis and Hans De Sterck. He completed his PhD in applied mathematics in October 2020, associated with the Department of mathematics and operations research at the University of Mons, Belgium. His PhD supervisor is Nicolas Gillis. He received a BEng degree, in Electronic and Communication Engineering, in 2014, and a MPhil degree, in Biomedical Engineering in 2016, all from the University of Hong Kong, Hong Kong. His research interests are general topics on the theory and application of optimization and matrix-tensor factorizations in machine learning.