Parametrization and convergence of a primal-dual block-coordinate approach to linearly-constrained nonsmooth optimization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916374484353024 |
|---|---|
| author | Bilenne, Olivier |
| author_facet | Bilenne, Olivier |
| contents | This note is concerned with the problem of minimizing a separable, convex, composite (smooth and nonsmooth) function subject to linear constraints. We study a randomized block-coordinate interpretation of the Chambolle-Pock primal-dual algorithm, based on inexact proximal gradient steps. A specificity of the considered algorithm is its robustness, as it converges even in the absence of strong duality or when the linear program is inconsistent. Using matrix preconditiong, we derive tight sublinear convergence rates with and without duality assumptions and for both the convex and the strongly convex settings. Our developments are extensions and particularizations of original algorithms proposed by Malitsky (2019) and Luke and Malitsky (2018). Numerical experiments are provided for an optimal transport problem of service pricing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16424 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parametrization and convergence of a primal-dual block-coordinate approach to linearly-constrained nonsmooth optimization Bilenne, Olivier Optimization and Control Distributed, Parallel, and Cluster Computing Multiagent Systems 49M29, 65Y20, 90C25, 49Q22 This note is concerned with the problem of minimizing a separable, convex, composite (smooth and nonsmooth) function subject to linear constraints. We study a randomized block-coordinate interpretation of the Chambolle-Pock primal-dual algorithm, based on inexact proximal gradient steps. A specificity of the considered algorithm is its robustness, as it converges even in the absence of strong duality or when the linear program is inconsistent. Using matrix preconditiong, we derive tight sublinear convergence rates with and without duality assumptions and for both the convex and the strongly convex settings. Our developments are extensions and particularizations of original algorithms proposed by Malitsky (2019) and Luke and Malitsky (2018). Numerical experiments are provided for an optimal transport problem of service pricing. |
| title | Parametrization and convergence of a primal-dual block-coordinate approach to linearly-constrained nonsmooth optimization |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Multiagent Systems 49M29, 65Y20, 90C25, 49Q22 |
| url | https://arxiv.org/abs/2408.16424 |