MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929727664553984 |
|---|---|
| author | Ang, Andersen De Sterck, Hans Vavasis, Stephen |
| author_facet | Ang, Andersen De Sterck, Hans Vavasis, Stephen |
| contents | We study the combination of proximal gradient descent with multigrid for solving a class of possibly nonsmooth strongly convex optimization problems. We propose a multigrid proximal gradient method called MGProx, which accelerates the proximal gradient method by multigrid, based on using 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 the MGProx update operator exhibits a fixed-point property. Next, we show that the coarse correction is a descent direction for the fine variable of the original fine level problem in the general nonsmooth case. Lastly, under some assumptions we provide the convergence rate for the algorithm. In the numerical tests on the Elastic Obstacle Problem, which is an example of nonsmooth convex optimization problem where multigrid method can be applied, we show that MGProx has a faster convergence speed than competing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_04077 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization Ang, Andersen De Sterck, Hans Vavasis, Stephen Optimization and Control 49J52, 49M37, 65K05, 65N55, 90C25, 90C30, 90C90 We study the combination of proximal gradient descent with multigrid for solving a class of possibly nonsmooth strongly convex optimization problems. We propose a multigrid proximal gradient method called MGProx, which accelerates the proximal gradient method by multigrid, based on using 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 the MGProx update operator exhibits a fixed-point property. Next, we show that the coarse correction is a descent direction for the fine variable of the original fine level problem in the general nonsmooth case. Lastly, under some assumptions we provide the convergence rate for the algorithm. In the numerical tests on the Elastic Obstacle Problem, which is an example of nonsmooth convex optimization problem where multigrid method can be applied, we show that MGProx has a faster convergence speed than competing methods. |
| title | MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization |
| topic | Optimization and Control 49J52, 49M37, 65K05, 65N55, 90C25, 90C30, 90C90 |
| url | https://arxiv.org/abs/2302.04077 |