Technical Report: A Totally Asynchronous Algorithm for Tracking Solutions to Time-Varying Convex Optimization Problems
arXiv:2110.06705
Abstract
This paper presents a decentralized algorithm for a team of agents to track time-varying fixed points that are the solutions to time-varying convex optimization problems. The algorithm is first-order, and it allows for total asynchrony in the communications and computations of all agents, i.e., all such operations can occur with arbitrary timing and arbitrary (finite) delays. Convergence rates are computed in terms of the communications and computations that agents execute, without specifying when they must occur. These rates apply to convergence to the minimum of each individual objective function, as well as agents' long-run behavior as their objective functions change. Then, to improve the usage of limited communication and computation resources, we optimize the timing of agents' operations relative to changes in their objective functions to minimize total fixed point tracking error over time. Simulation results are presented to illustrate these developments in practice and empirically assess their robustness to uncertainties in agents' update laws.
arXiv comment10 pages, 3 figures
References in corpus (5)
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
- A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
- Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
- Prediction-Correction Algorithms for Time-Varying Constrained Optimization
- Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees