Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics

DOI10.1007/S10957-021-01859-2zbMATH Open1497.37122arXiv2103.12675OpenAlexW3157095133MaRDI QIDQ2139279FDOQ2139279

Hédy Attouch, Z. Chbani, Jalal Fadili, H. Riahi

Publication date: 17 May 2022

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: In this paper, we propose in a Hilbertian setting a second-order time-continuous dynamic system with fast convergence guarantees to solve structured convex minimization problems with an affine constraint. The system is associated with the augmented Lagrangian formulation of the minimization problem. The corresponding dynamics brings into play three general time-varying parameters, each with specific properties, and which are respectively associated with viscous damping, extrapolation and temporal scaling. By appropriately adjusting these parameters, we develop a Lyapunov analysis which provides fast convergence properties of the values and of the feasibility gap. These results will naturally pave the way for developing corresponding accelerated ADMM algorithms, obtained by temporal discretization.

Full work available at URL: https://arxiv.org/abs/2103.12675

zbMATH Keywords

ADMMaugmented Lagrangianconvergence ratesLyapunov analysisconvex constrained minimizationdamped inertial dynamicsNesterov accelerated gradient methodtemporal scaling

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Convex programming (90C25) Management decision making, including multiple objectives (90B50) Dynamical systems in optimization and economics (37N40) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Approximation methods and numerical treatment of dynamical systems (37M99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Gradient methods for minimizing composite functions
• Fast Alternating Direction Optimization Methods
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Inertial Douglas-Rachford splitting for monotone inclusion problems
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• An inertial alternating direction method of multipliers
• An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems
• A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization
• Coupling Forward-Backward with Penalty Schemes and Parallel Splitting for Constrained Variational Inequalities
• Convex analysis and monotone operator theory in Hilbert spaces
• Convergence Rate Analysis of Several Splitting Schemes
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
• Some methods of speeding up the convergence of iteration methods
• A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
• Fast convex optimization via inertial dynamics with Hessian driven damping
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Accelerated Bregman method for linearly constrained \(\ell _1-\ell _2\) minimization
• Inexact accelerated augmented Lagrangian methods
• Stabilizability and Stability Robustness of State Derivative Feedback Controllers
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
• Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling
• First-order optimization algorithms via inertial systems with Hessian driven damping
• Stability of Over-Relaxations for the Forward-Backward Algorithm, Application to FISTA
• Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient
• Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity
• Asymptotic for a second-order evolution equation with convex potential andvanishing damping term
• Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule
• Convergence Rates of Inertial Forward-Backward Algorithms
• Fast Proximal Methods via Time Scaling of Damped Inertial Dynamics
• Second-order dynamical systems with penalty terms associated to monotone inclusions
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• Fast convex optimization via a third-order in time evolution equation

Cited In (13)

• Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem
• On the Arrow–Hurwicz differential system for linearly constrained convex minimization
• On Proximal Algorithms with Inertial Effects Beyond Monotonicity
• Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping
• A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem
• Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling
• Convergence of inertial dynamics driven by sums of potential and nonpotential operators with implicit Newton-like damping
• Optimal convergence rates for damped inertial gradient dynamics with flat geometries
• Fast convergence rates and trajectory convergence of a Tikhonov regularized inertial primal-dual dynamical system with time scaling and vanishing damping
• Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem
• Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems

This page was built for publication: Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2139279)