Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.05290 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917771551440896 |
|---|---|
| author | You, Pengcheng Liu, Yingzhu Mallada, Enrique |
| author_facet | You, Pengcheng Liu, Yingzhu Mallada, Enrique |
| contents | This work examines the conditions for asymptotic and exponential convergence of saddle flow dynamics of convex-concave functions. First, we propose an observability-based certificate for asymptotic convergence, directly bridging the gap between the invariant set in a LaSalle argument and the equilibrium set of saddle flows. This certificate generalizes conventional conditions for convergence, e.g., strict convexity-concavity, and leads to a novel state-augmentation method that requires minimal assumptions for asymptotic convergence. We also show that global exponential stability follows from strong convexity-strong concavity, providing a lower-bound estimate of the convergence rate. This insight also explains the convergence of proximal saddle flows for strongly convex-concave objective functions. Our results generalize to dynamics with projections on the vector field and have applications in solving constrained convex optimization via primal-dual methods. Based on these insights, we study four algorithms built upon different Lagrangian function transformations. We validate our work by applying these methods to solve a network flow optimization and a Lasso regression problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_05290 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Unified Analysis of Saddle Flow Dynamics: Stability and Algorithm Design You, Pengcheng Liu, Yingzhu Mallada, Enrique Optimization and Control This work examines the conditions for asymptotic and exponential convergence of saddle flow dynamics of convex-concave functions. First, we propose an observability-based certificate for asymptotic convergence, directly bridging the gap between the invariant set in a LaSalle argument and the equilibrium set of saddle flows. This certificate generalizes conventional conditions for convergence, e.g., strict convexity-concavity, and leads to a novel state-augmentation method that requires minimal assumptions for asymptotic convergence. We also show that global exponential stability follows from strong convexity-strong concavity, providing a lower-bound estimate of the convergence rate. This insight also explains the convergence of proximal saddle flows for strongly convex-concave objective functions. Our results generalize to dynamics with projections on the vector field and have applications in solving constrained convex optimization via primal-dual methods. Based on these insights, we study four algorithms built upon different Lagrangian function transformations. We validate our work by applying these methods to solve a network flow optimization and a Lasso regression problem. |
| title | A Unified Analysis of Saddle Flow Dynamics: Stability and Algorithm Design |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.05290 |