Analysis and design of optimization algorithms via integral quadratic constraints
From MaRDI portal
Publication:3465237
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.
Recommendations
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
- Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs
- Convex Synthesis of Accelerated Gradient Algorithms
- Analysis of optimization algorithms via sum-of-squares
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Absolute stability of nonlinear systems of automatic control
- Dissipative dynamical systems. I: General theory
- Dissipative dynamical systems. II: Linear systems with quadratic supply rates
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Dualities in convex algebraic geometry
- Efficiency of coordinate descent methods on huge-scale optimization problems
- First-order methods of smooth convex optimization with inexact oracle
- Gradient methods for minimizing composite functions
- Graph implementations for nonsmooth convex programs
- scientific article; zbMATH DE number 427959 (Why is no real title available?)
- scientific article; zbMATH DE number 432503 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 47864 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3249151 (Why is no real title available?)
- scientific article; zbMATH DE number 3100566 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Linear Matrix Inequalities in System and Control Theory
- LYAPUNOV FUNCTIONS FOR THE PROBLEM OF LUR'E IN AUTOMATIC CONTROL
- Method of centers for minimizing generalized eigenvalues
- Nonconvex optimization problem: The infinite-horizon linear-quadratic control problem with quadratic constraints
- Nonlinear systems.
- Performance of first-order methods for smooth convex minimization: a novel approach
- Robust Stochastic Approximation Approach to Stochastic Programming
- Semidefinite programming relaxations and algebraic optimization in control
- Stability Analysis With Dissipation Inequalities and Integral Quadratic Constraints
- Stability Conditions for Systems with Monotone and Slope-Restricted Nonlinearities
- System analysis via integral quadratic constraints
- Templates for convex cone problems with applications to sparse signal recovery
- The complex structured singular value
- The long-step method of analytic centers for fractional problems
- Transient cool-down of a porous medium in pulsating flow
- Zames-Falb Multipliers for Quadratic Programming
Cited in
(only showing first 100 items - show all)- Specialized fast algorithms for IQC feasibility and optimization problems.
- Optimal deterministic algorithm generation
- Adaptive restart of the optimized gradient method for convex optimization
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Convergence of first-order methods via the convex conjugate
- Stability analysis by dynamic dissipation inequalities: on merging frequency-domain techniques with time-domain conditions
- Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
- Analysis of biased stochastic gradient descent using sequential semidefinite programs
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Bounds for the tracking error of first-order online optimization methods
- Analysis of optimization algorithms via sum-of-squares
- Bearing-only distributed localization: a unified barycentric approach
- Iterative pre-conditioning for expediting the distributed gradient-descent method: the case of linear least-squares problem
- Understanding the acceleration phenomenon via high-resolution differential equations
- From differential equation solvers to accelerated first-order methods for convex optimization
- A control-theoretic perspective on optimal high-order optimization
- Passivity-based analysis of the ADMM algorithm for constraint-coupled optimization
- An adaptive Polyak heavy-ball method
- On the convergence analysis of aggregated heavy-ball method
- Generating Nesterov's accelerated gradient algorithm by using optimal control theory for optimization
- A frequency-domain analysis of inexact gradient methods
- Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- A regularization interpretation of the proximal point method for weakly convex functions
- Efficient first-order methods for convex minimization: a constructive approach
- A simple PID-based strategy for particle swarm optimization algorithm
- A review of nonlinear FFT-based computational homogenization methods
- Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization
- Regularized nonlinear acceleration
- On polarization-based schemes for the FFT-based computational homogenization of inelastic materials
- Explicit stabilised gradient descent for faster strongly convex optimisation
- Proximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints
- On data-driven stabilization of systems with nonlinearities satisfying quadratic constraints
- Perturbed Fenchel duality and first-order methods
- Mini-workshop: Analysis of data-driven optimal control. Abstracts from the mini-workshop held May 9--15, 2021 (hybrid meeting)
- On lower and upper bounds in smooth and strongly convex optimization
- Zames-Falb multipliers for absolute stability: from O'Shea's contribution to convex searches
- Search direction correction with normalized gradient makes first-order methods faster
- Generalizing the optimized gradient method for smooth convex minimization
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- An optimal first order method based on optimal quadratic averaging
- Convergence rates of proximal gradient methods via the convex conjugate
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- scientific article; zbMATH DE number 1424228 (Why is no real title available?)
- Projected dynamical systems on irregular, non-Euclidean domains for nonlinear optimization
- A general system of differential equations to model first-order adaptive algorithms
- Connections between Georgiou and Smith's robust stability type theorems and the nonlinear small-gain theorems
- The connections between Lyapunov functions for some optimization algorithms and differential equations
- Continuous time analysis of momentum methods
- Optimization with momentum: dynamical, control-theoretic, and symplectic perspectives
- A unified analysis of first-order methods for smooth games via integral quadratic constraints
- A Lyapunov analysis of accelerated methods in optimization
- Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
- Convex Synthesis of Accelerated Gradient Algorithms
- Higher-order power methods with momentum for solving the limiting probability distribution vector of higher-order Markov chains
- Analysis of a generalised expectation-maximisation algorithm for Gaussian mixture models: a control systems perspective
- scientific article; zbMATH DE number 7626757 (Why is no real title available?)
- Complexity analysis for optimization methods
- Zames–Falb multipliers for convergence rate: motivating example and convex searches
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Differentially Private Accelerated Optimization Algorithms
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- Convergence rates of the heavy ball method for quasi-strongly convex optimization
- Design of distributed and robust optimization algorithms. A systems theoretic approach
- Contractivity of Runge-Kutta methods for convex gradient systems
- Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
- On the convergence analysis of the optimized gradient method
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Multiscale analysis of accelerated gradient methods
- On the asymptotic linear convergence speed of Anderson acceleration, Nesterov acceleration, and nonlinear GMRES
- On the Convergence Rate of Incremental Aggregated Gradient Algorithms
- Exact worst-case performance of first-order methods for composite convex optimization
- Robustness analysis of uncertain discrete-time systems with dissipation inequalities and integral quadratic constraints
- The common-directions method for regularized empirical risk minimization
- An introduction to continuous optimization for imaging
- Robust accelerated gradient methods for smooth strongly convex functions
- An optimal gradient method for smooth strongly convex minimization
- A zeroing neural dynamics based acceleration optimization approach for optimizers in deep neural networks
- Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- A fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint
- On the necessity and sufficiency of discrete-time O'Shea-Zames-Falb multipliers
- Fast gradient method for low-rank matrix estimation
- A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Optimal step length for the maximal decrease of a self-concordant function by the Newton method
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
- Heavy-ball-based hard thresholding algorithms for sparse signal recovery
- Uniting Nesterov and heavy ball methods for uniform global asymptotic stability of the set of minimizers
- Understanding a Class of Decentralized and Federated Optimization Algorithms: A Multirate Feedback Control Perspective
- A forward-backward algorithm with different inertial terms for structured non-convex minimization problems
- Principled analyses and design of first-order methods with inexact proximal operators
- Convergence of gradient algorithms for nonconvex \(C^{1+ \alpha}\) cost functions
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Computation of invariant sets for discrete‐time uncertain systems
- A multivariate adaptive gradient algorithm with reduced tuning efforts
- Lippmann-Schwinger solvers for the computational homogenization of materials with pores
- On the Barzilai-Borwein basic scheme in FFT-based computational homogenization
- Nonlinear optimization filters for stochastic time-varying convex optimization
This page was built for publication: Analysis and design of optimization algorithms via integral quadratic constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3465237)
