# Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems

arXiv: https://arxiv.org/abs/2408.15969 · HTML: https://mlsanity.com/paper/2408.15969/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 78 references that are in the map.
- First posted on arXiv 28 Aug 2024.

## Builds on (most cited first, 30 of 33)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [A General Analysis of the Convergence of ADMM](https://mlsanity.com/paper/1502.02009/) (2015)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [Convergence Rate of Distributed ADMM over Networks](https://mlsanity.com/paper/1601.00194/) (2016)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Parallel Multi-Block ADMM with o(1/k) Convergence](https://mlsanity.com/paper/1312.3040/) (2013)
- [A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization](https://mlsanity.com/paper/1706.02882/) (2017)
- [On the Exponential Stability of Primal-Dual Gradient Dynamics](https://mlsanity.com/paper/1803.01825/) (2018)
- [The proximal augmented Lagrangian method for nonsmooth composite optimization](https://mlsanity.com/paper/1610.04514/) (2016)
- [Asymptotic convergence of constrained primal-dual dynamics](https://mlsanity.com/paper/1510.02150/) (2015)
- [Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators](https://mlsanity.com/paper/1602.08729/) (2016)
- [On the Global Linear Convergence of the ADMM with Multi-Block Variables](https://mlsanity.com/paper/1408.4266/) (2014)
- [The role of convexity on saddle-point dynamics: Lyapunov function and robustness](https://mlsanity.com/paper/1608.08586/) (2016)
- [Design and Stability of Load-Side Primary Frequency Control in Power Systems](https://mlsanity.com/paper/1305.0585/) (2013)
- [Contraction and Robustness of Continuous Time Primal-Dual Dynamics](https://mlsanity.com/paper/1803.05975/) (2018)
- [Distributed and time-varying primal-dual dynamics via contraction analysis](https://mlsanity.com/paper/2003.12665/) (2020)
- [Semi-Global Exponential Stability of Augmented Primal-Dual Gradient Dynamics for Constrained Convex Optimization](https://mlsanity.com/paper/1903.09580/) (2019)
- [Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity](https://mlsanity.com/paper/1504.03087/) (2015)
- [Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics](https://mlsanity.com/paper/2103.12675/) (2021)
- [New Primal-Dual Proximal Algorithm for Distributed Optimization](https://mlsanity.com/paper/1605.01986/) (2016)
- [Stochastic dynamical modeling of turbulent flows](https://mlsanity.com/paper/1908.09487/) (2019)
- ["Second-Order Primal'' + "First-Order Dual'' Dynamical Systems with Time Scaling for Linear Equality Constrained Convex Optimization Problems](https://mlsanity.com/paper/2103.12931/) (2021)
- [Low-complexity modeling of partially available second-order statistics: theory and an efficient matrix completion algorithm](https://mlsanity.com/paper/1412.3399/) (2014)
- [Color of turbulence](https://mlsanity.com/paper/1602.05105/) (2016)

## Abstract (arXiv)

We examine stability properties of primal-dual gradient flow dynamics for composite convex optimization problems with multiple, possibly nonsmooth, terms in the objective function under the generalized consensus constraint. The proposed dynamics are based on the proximal augmented Lagrangian and they provide a viable alternative to ADMM which faces significant challenges from both analysis and implementation viewpoints in large-scale multi-block scenarios. In contrast to customized algorithms with individualized convergence guarantees, we develop a systematic approach for solving a broad class of challenging composite optimization problems. We leverage various structural properties to establish global (exponential) convergence guarantees for the proposed dynamics. Our assumptions are much weaker than those required to prove (exponential) stability of primal-dual dynamics as well as (linear) convergence of discrete-time methods such as standard two-block and multi-block ADMM and EXTRA algorithms. Finally, we show necessity of some of our structural assumptions for exponential stability and provide computational experiments to demonstrate the convenience of the proposed approach for parallel and distributed computing applications.