Automated tight Lyapunov analysis for first-order methods

DOI10.1007/S10107-024-02061-8MaRDI QIDQ6665382zbMATH OpenFDO

Authors Manu Upadhyaya, Sebastian Banert, Adrien B. Taylor, Pontus Giselsson

Publication date 17 January 2025

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-024-02061-8

zbMATH Keywords

convex optimizationfirst-order methodsLyapunov functionsperformance estimationquadratic constraintssemidefinite programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• A first-order primal-dual algorithm for convex problems with applications to imaging
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
• A three-operator splitting scheme and its optimization applications
• Analysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
• Analysis and design of optimization algorithms via integral quadratic constraints
• Conjugate duality in convex optimization
• Convex analysis and monotone operator theory in Hilbert spaces
• Data-driven nonsmooth optimization
• Exact algorithms for linear matrix inequalities
• Exact worst-case performance of first-order methods for composite convex optimization
• First-order methods in optimization
• Fixing and extending some recent results on the ADMM algorithm
• Lectures on convex optimization
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the ergodic convergence rates of a first-order primal-dual algorithm
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Operator splitting performance estimation: tight contraction factors and optimal parameter selection
• Optimal complexity and certification of Bregman first-order methods
• Performance of first-order methods for smooth convex minimization: a novel approach
• Principled analyses and design of first-order methods with inexact proximal operators
• Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• System analysis via integral quadratic constraints
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

Cited in

(2)

• A primal-dual splitting algorithm with convex combination and larger step sizes for composite monotone inclusion problems
• The Chambolle-Pock method converges weakly with \(\theta >1/2\) and \(\tau \sigma \Vert L\Vert^2<4/(1+2\theta )\)

This page was built for publication: Automated tight Lyapunov analysis for first-order methods

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