Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints

Abstract

This manuscript develops a new framework to analyze and design iterative optimization algorithms built on the notion of Integral Quadratic Constraints (IQC) from robust control theory. IQCs provide sufficient conditions for the stability of complicated interconnected systems, and these conditions can be checked by semidefinite programming. We discuss how to adapt IQC theory to study optimization algorithms, proving new inequalities about convex functions and providing a version of IQC theory adapted for use by optimization researchers. Using these inequalities, we derive numerical upper bounds on convergence rates for the gradient method, the heavy-ball method, Nesterov's accelerated method, and related variants by solving small, simple semidefinite programming problems. We also briefly show how these techniques can be used to search for optimization algorithms with desired performance characteristics, establishing a new methodology for algorithm design.

The previous version of this paper quoted the wrong rate of Nesterov's optimal method when applied to strongly convex functions. With this correction, our bounds are now slightly better than those previously derived for Nesterov's method

Cited by in corpus (48)

• A Variational Perspective on Accelerated Methods in Optimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• The proximal augmented Lagrangian method for nonsmooth composite optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• From differential equation solvers to accelerated first-order methods for convex optimization
• Acceleration Methods
• Generalizing the optimized gradient method for smooth convex minimization
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• Model predictive control for linear uncertain systems using integral quadratic constraints
• Control Barrier Functions With Unmodeled Dynamics Using Integral Quadratic Constraints
• On the convergence analysis of the optimized gradient method
• Convex searches for discrete-time Zames-Falb multipliers
• The Analysis of Optimization Algorithms, A Dissipativity Approach
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• On the Powerball Method for Optimization
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Phase limitations of Zames-Falb multipliers
• A System Theoretical Perspective to Gradient-Tracking Algorithms for Distributed Quadratic Optimization
• Input-Output Performance of Linear-Quadratic Saddle-Point Algorithms with Application to Distributed Resource Allocation Problems
• Duality bounds for discrete-time Zames-Falb multipliers
• Internal Model-Based Online Optimization
• Differentially Private Accelerated Optimization Algorithms
• A systematic approach to Lyapunov analyses of continuous-time models in convex optimization
• Bounds for the tracking error of first-order online optimization methods
• Iterative Pre-Conditioning for Expediting the Gradient-Descent Method: The Distributed Linear Least-Squares Problem
• Time-Varying Convex Optimization: A Contraction and Equilibrium Tracking Approach
• Automated tight Lyapunov analysis for first-order methods
• A new framework for constrained optimization via feedback control of Lagrange multipliers
• Automatic Performance Estimation for Decentralized Optimization
• Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• Self-Healing First-Order Distributed Optimization
• Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems
• Interpolation Constraints for Computing Worst-Case Bounds in Performance Estimation Problems
• Rapid Transitions with Robust Accelerated Delayed Self Reinforcement for Consensus-Based Networks
• Incentives and co-evolution: Steering linear dynamical systems with noncooperative agents
• Exponential Stability of Parametric Optimization-Based Controllers via Lur'e Contractivity
• Induced Norm Analysis of Linear Systems for Nonnegative Input Signals
• Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems
• A Globally Convergent Gradient Method with Momentum
• Frequency Domain Stability Conditions for Hybrid AC/DC Systems
• About some works of Boris Polyak on convergence of gradient methods and their development
• Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
• Optimization Method Based On Optimal Control
• European Satellite Benchmark for Control Education and Industrial Training
• Automated algorithm design for convex optimization problems with linear equality constraints
• SHANG++: Robust Stochastic Acceleration under Multiplicative Noise
• Tannenbaum's gain-margin optimization meets Polyak's heavy-ball algorithm