Time-Varying Convex Optimization via Time-Varying Averaged Operators

Abstract

Devising efficient algorithms that track the optimizers of continuously varying convex optimization problems is key in many applications. A possible strategy is to sample the time-varying problem at constant rate and solve the resulting time-invariant problem. This can be too computationally burdensome in many scenarios. An alternative strategy is to set up an iterative algorithm that generates a sequence of approximate optimizers, which are refined every time a new sampled time-invariant problem is available by one iteration of the algorithm. These types of algorithms are called running. A major limitation of current running algorithms is their key assumption of strong convexity and strong smoothness of the time-varying convex function. In addition, constraints are only handled in simple cases. This limits the current capability for running algorithms to tackle relevant problems, such as ${\ell }_1$-regularized optimization programs. In this paper, these assumptions are lifted by leveraging averaged operator theory and a fairly comprehensive framework for time-varying convex optimization is presented. In doing so, new results characterizing the convergence of running versions of a number of widely used algorithms are derived.

arXiv comment30 pages, 2 figures -- version 3: add three new sections with additional results and background material

References in corpus (8)

• Design and Stability of Load-Side Primary Frequency Control in Power Systems
• Embedded Online Optimization for Model Predictive Control at Megahertz Rates
• Splitting methods with variable metric for KL functions
• Distributed Maximum Likelihood Sensor Network Localization
• A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
• Prediction-Correction Algorithms for Time-Varying Constrained Optimization
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry

Cited by in corpus (10)

• Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• Bounds for the tracking error of first-order online optimization methods
• Nonstationary Nonparametric Online Learning: Balancing Dynamic Regret and Model Parsimony
• A Continuous-Time Nesterov Accelerated Gradient Method for Centralized and Distributed Online Convex Optimization
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• Error Bounds and Applications for Stochastic Approximation with Non-Decaying Gain
• Wide and Deep Graph Neural Networks with Distributed Online Learning
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Time-Varying Optimization: Algorithms and Engineering Applications