Proximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints

DOI10.1016/J.AUTOMATICA.2020.109311zbMATH Open1461.93433arXiv1908.09043OpenAlexW3097133297WikidataQ115583226 ScholiaQ115583226MaRDI QIDQ2662276FDOQ2662276

Authors: Sepideh Hassan-Moghaddam, Mihailo R. Jovanović 

Publication date: 12 April 2021

Published in: Automatica (Search for Journal in Brave)

Abstract: Many large-scale and distributed optimization problems can be brought into a composite form in which the objective function is given by the sum of a smooth term and a nonsmooth regularizer. Such problems can be solved via a proximal gradient method and its variants, thereby generalizing gradient descent to a nonsmooth setup. In this paper, we view proximal algorithms as dynamical systems and leverage techniques from control theory to study their global properties. In particular, for problems with strongly convex objective functions, we utilize the theory of integral quadratic constraints to prove the global exponential stability of the equilibrium points of the differential equations that govern the evolution of proximal gradient and Douglas-Rachford splitting flows. In our analysis, we use the fact that these algorithms can be interpreted as variable-metric gradient methods on the suitable envelopes and exploit structural properties of the nonlinear terms that arise from the gradient of the smooth part of the objective function and the proximal operator associated with the nonsmooth regularizer. We also demonstrate that these envelopes can be obtained from the augmented Lagrangian associated with the original nonsmooth problem and establish conditions for global exponential convergence even in the absence of strong convexity.

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

Recommendations

• Exponential stability of partial primal-dual gradient dynamics with nonsmooth objective functions
• Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
• Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
• A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems
• Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization

zbMATH Keywords

nonsmooth optimizationnonlinear dynamicsDouglas-Rachford splittingglobal exponential stabilityproximal algorithmsprimal-dual methodsintegral quadratic constraints (IQCs)proximal augmented Lagrangiancontrol for optimizationforward-backward envelope

Mathematics Subject Classification ID

Existence theories for free problems in one independent variable (49J05) Exponential stability (93D23)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Analysis and design of optimization algorithms via integral quadratic constraints
• System analysis via integral quadratic constraints
• Distributed Subgradient Methods for Multi-Agent Optimization
• Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations
• Title not available (Why is that?)
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• Stability of primal-dual gradient dynamics and applications to network optimization
• Asymptotic convergence of constrained primal-dual dynamics
• Title not available (Why is that?)
• The Role of Convexity in Saddle-Point Dynamics: Lyapunov Function and Robustness
• A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization
• The Proximal Augmented Lagrangian Method for Nonsmooth Composite Optimization
• A variational perspective on accelerated methods in optimization
• A dynamical systems approach to constrained minimization
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
• Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
• Exponential Decay Rate Conditions for Uncertain Linear Systems Using Integral Quadratic Constraints

Cited In (7)

• Passivity-based analysis of the ADMM algorithm for constraint-coupled optimization
• Nonlinear optimization filters for stochastic time-varying convex optimization
• A new dynamical system with self-adaptive dynamical stepsize for pseudomonotone mixed variational inequalities
• Neurodynamic approaches for multi-agent distributed optimization
• Exponential stability of partial primal-dual gradient dynamics with nonsmooth objective functions
• A frequency-domain analysis of inexact gradient methods
• A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem

This page was built for publication: Proximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints

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