The Chambolle-Pock method also converges weakly with $0 < θ\le 1$ and $τσ\|L\|^{2} < 4θ(2-θ)/(1 - 2θ+ 9θ^{2} - 4θ^{3})$
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911574434775040 |
|---|---|
| author | Upadhyaya, Manu |
| author_facet | Upadhyaya, Manu |
| contents | The Chambolle-Pock method, also known as the primal-dual hybrid gradient method, is a standard first-order algorithm for convex-concave saddle-point problems and composite convex optimization involving two proper, lower semicontinuous, convex functions and a bounded linear operator $L$. We study its convergence in real Hilbert spaces for step sizes $τ,σ>0$ and relaxation parameter $0<θ\le 1$. We prove that, if $τσ|L|^{2} \leq 4θ(2-θ)/(1 - 2θ+ 9θ^{2} - 4θ^{3})$, then the ergodic duality gap converges at rate $O(1/k)$, and that, when the inequality is strict, the primal-dual iterates converge weakly to a KKT point. In particular, this extends the weak-convergence theory to the previously unexplored regime $0<θ\le 1/2$. The proof is based on a Lyapunov function that remains uniformly valid over the entire interval $0<θ\le 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06423 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Chambolle-Pock method also converges weakly with $0 < θ\le 1$ and $τσ\|L\|^{2} < 4θ(2-θ)/(1 - 2θ+ 9θ^{2} - 4θ^{3})$ Upadhyaya, Manu Optimization and Control 47J25, 49M29, 65K05, 90C25, 93D30 The Chambolle-Pock method, also known as the primal-dual hybrid gradient method, is a standard first-order algorithm for convex-concave saddle-point problems and composite convex optimization involving two proper, lower semicontinuous, convex functions and a bounded linear operator $L$. We study its convergence in real Hilbert spaces for step sizes $τ,σ>0$ and relaxation parameter $0<θ\le 1$. We prove that, if $τσ|L|^{2} \leq 4θ(2-θ)/(1 - 2θ+ 9θ^{2} - 4θ^{3})$, then the ergodic duality gap converges at rate $O(1/k)$, and that, when the inequality is strict, the primal-dual iterates converge weakly to a KKT point. In particular, this extends the weak-convergence theory to the previously unexplored regime $0<θ\le 1/2$. The proof is based on a Lyapunov function that remains uniformly valid over the entire interval $0<θ\le 1$. |
| title | The Chambolle-Pock method also converges weakly with $0 < θ\le 1$ and $τσ\|L\|^{2} < 4θ(2-θ)/(1 - 2θ+ 9θ^{2} - 4θ^{3})$ |
| topic | Optimization and Control 47J25, 49M29, 65K05, 90C25, 93D30 |
| url | https://arxiv.org/abs/2604.06423 |