A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate

Abstract

This paper provides a self-contained ordinary differential equation solver approach for separable convex optimization problems. A novel primal-dual dynamical system with built-in time rescaling factors is introduced, and the exponential decay of a tailored Lyapunov function is established. Then several time discretizations of the continuous model are considered and analyzed via a unified discrete Lyapunov function. Moreover, two families of accelerated proximal alternating direction methods of multipliers are obtained, and nonergodic optimal mixed-type convergence rates shall be proved for the primal objective residual, the feasibility violation and the Lagrangian gap. Finally, numerical experiments are provided to validate the practical performances.

References in corpus (23)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Generalized Symmetric ADMM for Separable Convex Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• From differential equation solvers to accelerated first-order methods for convex optimization
• A Dynamical Systems Perspective on Nesterov Acceleration
• Self Equivalence of the Alternating Direction Method of Multipliers
• ADMM and Accelerated ADMM as Continuous Dynamical Systems
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming
• On the Global Linear Convergence of the ADMM with Multi-Block Variables
• Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization
• First order optimization methods based on Hessian-driven Nesterov accelerated gradient flow
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Proximal Alternating Penalty Algorithms for Constrained Convex Optimization
• A sparse semismooth Newton based augmented Lagrangian method for large-scale support vector machines
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• Accelerated differential inclusion for convex optimization
• Inertial primal-dual methods for linear equality constrained convex optimization problems
• Perturbed primal-dual dynamics with damping and time scaling coefficients for affine constrained convex optimization problems
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates