Back to Search
Start Over
Unified linear convergence of first-order primal-dual algorithms for saddle point problems.
- Source :
- Optimization Letters; Jul2022, Vol. 16 Issue 6, p1675-1700, 26p
- Publication Year :
- 2022
-
Abstract
- In this paper, we study the linear convergence of several well-known first-order primal-dual methods for solving a class of convex-concave saddle point problems. We first unify the convergence analysis of these methods and prove the O(1/N) convergence rates of the primal-dual gap generated by these methods in the ergodic sense, where N counts the number of iterations. Under a mild calmness condition, we further establish the global Q-linear convergence rate of the distances between the iterates generated by these methods and the solution set, and show the R-linear rate of the iterates in the nonergodic sense. Moreover, we demonstrate that the matrix games, fused lasso and constrained TV- ℓ 2 image restoration models as application examples satisfy this calmness condition. Numerical experiments on fused lasso demonstrate the linear rates for these methods. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 18624472
- Volume :
- 16
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- Optimization Letters
- Publication Type :
- Academic Journal
- Accession number :
- 157279332
- Full Text :
- https://doi.org/10.1007/s11590-021-01832-y