Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915315930103808 |
|---|---|
| author | Apidopoulos, Vassilis Molinari, Cesare Peypouquet, Juan Villa, Silvia |
| author_facet | Apidopoulos, Vassilis Molinari, Cesare Peypouquet, Juan Villa, Silvia |
| contents | We introduce and analyze a continuous primal-dual dynamical system in the context of the minimization problem $f(x)+g(Ax)$, where $f$ and $g$ are convex functions and $A$ is a linear operator. In this setting, the trajectories of the Arrow-Hurwicz continuous flow may not converge, accumulating at points that are not solutions. Our proposal is inspired by the primal-dual algorithm of Chambolle and Pock (2011), where convergence and splitting on the primal-dual variable are ensured by adequately preconditioning the proximal-point algorithm. We consider a family of preconditioners, which are allowed to depend on time and on the operator $A$, but not on the functions $f$ and $g$, and analyze asymptotic properties of the corresponding preconditioned flow. Fast convergence rates for the primal-dual gap and optimality of its (weak) limit points are obtained, in the general case, for asymptotically antisymmetric preconditioners, and, in the case of linearly constrained optimization problems, under milder hypotheses. Numerical examples support our theoretical findings, especially in favor of the antisymmetric preconditioners. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates Apidopoulos, Vassilis Molinari, Cesare Peypouquet, Juan Villa, Silvia Optimization and Control 34D05, 65K05, 65K10, 90C25 We introduce and analyze a continuous primal-dual dynamical system in the context of the minimization problem $f(x)+g(Ax)$, where $f$ and $g$ are convex functions and $A$ is a linear operator. In this setting, the trajectories of the Arrow-Hurwicz continuous flow may not converge, accumulating at points that are not solutions. Our proposal is inspired by the primal-dual algorithm of Chambolle and Pock (2011), where convergence and splitting on the primal-dual variable are ensured by adequately preconditioning the proximal-point algorithm. We consider a family of preconditioners, which are allowed to depend on time and on the operator $A$, but not on the functions $f$ and $g$, and analyze asymptotic properties of the corresponding preconditioned flow. Fast convergence rates for the primal-dual gap and optimality of its (weak) limit points are obtained, in the general case, for asymptotically antisymmetric preconditioners, and, in the case of linearly constrained optimization problems, under milder hypotheses. Numerical examples support our theoretical findings, especially in favor of the antisymmetric preconditioners. |
| title | Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates |
| topic | Optimization and Control 34D05, 65K05, 65K10, 90C25 |
| url | https://arxiv.org/abs/2506.00501 |