Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911208776400896 |
|---|---|
| author | Melcher, Cody Jalilzadeh, Afrooz Hamedani, Erfan Yazdandoost |
| author_facet | Melcher, Cody Jalilzadeh, Afrooz Hamedani, Erfan Yazdandoost |
| contents | In this paper, we study saddle point (SP) problems, focusing on convex-concave optimization involving functions that satisfy either two-sided quadratic functional growth (QFG) or two-sided quadratic gradient growth (QGG)--novel conditions tailored specifically for SP problems as extensions of quadratic growth conditions in minimization. These conditions relax the traditional requirement of strong convexity-strong concavity, thereby encompassing a broader class of problems. We propose a generalized accelerated primal-dual (GAPD) algorithm to solve SP problems with non-bilinear objective functions, unifying and extending existing methods. We prove that our method achieves a linear convergence rate under these relaxed conditions. Additionally, we provide examples of structured SP problems that satisfy either two-sided QFG or QGG, demonstrating the practical applicability and relevance of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11990 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth Melcher, Cody Jalilzadeh, Afrooz Hamedani, Erfan Yazdandoost Optimization and Control In this paper, we study saddle point (SP) problems, focusing on convex-concave optimization involving functions that satisfy either two-sided quadratic functional growth (QFG) or two-sided quadratic gradient growth (QGG)--novel conditions tailored specifically for SP problems as extensions of quadratic growth conditions in minimization. These conditions relax the traditional requirement of strong convexity-strong concavity, thereby encompassing a broader class of problems. We propose a generalized accelerated primal-dual (GAPD) algorithm to solve SP problems with non-bilinear objective functions, unifying and extending existing methods. We prove that our method achieves a linear convergence rate under these relaxed conditions. Additionally, we provide examples of structured SP problems that satisfy either two-sided QFG or QGG, demonstrating the practical applicability and relevance of our approach. |
| title | Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.11990 |