Analysis and Synthesis of Switched Optimization Algorithms

2025/10/24 by Miller, Jared, Jakob, Fabian, Scherer, Carsten +1
#FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2510.21490

Abstract

Deployment of optimization algorithms on networked systems face challenges associated with time delays and corruptions. One particular instance is the presence of time-varying delays arising from factors such as packet drops and irregular sampling. Fixed time delays can destabilize gradient descent algorithms, and this degradation is exacerbated by time-varying delays. This work concentrates on the analysis and creation of discrete-time optimization algorithms with certified exponential convergence rates that are robust against switched uncertainties between the optimizer and the gradient oracle. These optimization algorithms are implemented by a switch-scheduled output feedback controllers. Rate variation and sawtooth behavior (packet drops) in time-varying delays can be imposed through constraining switching sequences. Analysis is accomplished by bisection in the convergence rate to find Zames-Falb filter coefficents. Synthesis is performed by alternating between a filter coefficient search for a fixed controller, and a controller search for fixed multipliers.

Citations

• A Linear Parameter-Varying Framework for the Analysis of Time-Varying Optimization Algorithms
• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
• Optimization Algorithm Synthesis based on Integral Quadratic Constraints: A Tutorial
• Robust Exponential Stability and Invariance Guarantees with General Dynamic O'Shea-Zames-Falb Multipliers
• The distributed dual ascent algorithm is robust to asynchrony
• Consensus-Based Distributed Estimation in the Presence of Heterogeneous,\n Time-Invariant Delays
• Convex Synthesis of Accelerated Gradient Algorithms
• Robustness of accelerated first-order algorithms for strongly convex\n optimization problems
• Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach
• Exponential Convergence Bounds using Integral Quadratic Constraints
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
• Uniform stabilization of discrete-time switched and Markovian jump linear systems

Cited by

• AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods

Related

• Optimization via First-Order Switching Methods: Skew-Symmetric Dynamics and Optimistic Discretization
• Decomposition Principles and Online Learning in Cross-Layer Optimization for Delay-Sensitive Applications
• Temporal Variabilities Limit Convergence Rates in Gradient-Based Online Optimization
• Asynchronous speedup in decentralized optimization
• Optimization over time-varying networks with unbounded delays