Time-Varying Convex Optimization: A Contraction and Equilibrium Tracking Approach

Abstract

In this article, we provide a novel and broadly-applicable contraction-theoretic approach to continuous-time time-varying convex optimization. For any parameter-dependent contracting dynamics, we show that the tracking error is asymptotically proportional to the rate of change of the parameter and that the proportionality constant is upper bounded by Lipschitz constant in which the parameter appears divided by the contraction rate of the dynamics squared. We additionally establish that augmenting any parameter-dependent contracting dynamics with a feedforward prediction term ensures that the tracking error vanishes exponentially quickly. To apply these results to time-varying convex optimization, we establish the strong infinitesimal contractivity of dynamics solving three canonical problems: monotone inclusions, linear equality-constrained problems, and composite minimization problems. For each case, we derive the sharpest-known contraction rates and provide explicit bounds on the tracking error between solution trajectories and minimizing trajectories. We validate our theoretical results on two numerical examples and on an application to control barrier function-based controller design that involves real hardware.

References in corpus (12)

• Control Barrier Function Based Quadratic Programs for Safety Critical Systems
• Recent Advances in Physical Reservoir Computing: A Review
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
• On the Exponential Stability of Primal-Dual Gradient Dynamics
• Nash and Wardrop equilibria in aggregative games with coupling constraints
• The proximal augmented Lagrangian method for nonsmooth composite optimization
• Prediction-Correction Algorithms for Time-Varying Constrained Optimization
• Optimization and Learning with Information Streams: Time-varying Algorithms and Applications
• Non-Euclidean Contraction Theory for Robust Nonlinear Stability
• The Analysis of Optimization Algorithms, A Dissipativity Approach
• Non-Euclidean Contraction Analysis of Continuous-Time Neural Networks