A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM

Abstract

Recently, there has been great interest in connections between continuous-time dynamical systems and optimization methods, notably in the context of accelerated methods for smooth and unconstrained problems. In this paper we extend this perspective to nonsmooth and constrained problems by obtaining differential inclusions associated to novel accelerated variants of the alternating direction method of multipliers (ADMM). Through a Lyapunov analysis, we derive rates of convergence for these dynamical systems in different settings that illustrate an interesting tradeoff between decaying versus constant damping strategies. We also obtain modified equations capturing fine-grained details of these methods, which have improved stability and preserve the leading order convergence rates. An extension to general nonlinear equality and inequality constraints in connection with singular perturbation theory is provided.

Last version was completely rewritten. New results for modified/perturbed equations, constraints, and singular perturbation theory. Matches the version to appear on IEEE Transactions on Automatic Control

References in corpus (6)

• Hamiltonian Descent Methods
• On dissipative symplectic integration with applications to gradient-based optimization
• Convergence of proximal solutions for evolution inclusions with time-dependent maximal monotone operators
• Conformal Symplectic and Relativistic Optimization
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Optimization on manifolds: A symplectic approach

Cited by in corpus (8)

• Hamiltonian Descent Methods
• User Dynamics-Aware Edge Caching and Computing for Mobile Virtual Reality
• On dissipative symplectic integration with applications to gradient-based optimization
• Conformal Symplectic and Relativistic Optimization
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents
• Finite-Time Convergence of Continuous-Time Optimization Algorithms via Differential Inclusions
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate