Internal Model-Based Online Optimization
arXiv:2205.13932 · doi:10.1109/TAC.2023.3297504
Abstract
In this paper we propose a model-based approach to the design of online optimization algorithms, with the goal of improving the tracking of the solution trajectory (trajectories) w.r.t. state-of-the-art methods. We focus first on quadratic problems with a time-varying linear term, and use digital control tools (a robust internal model principle) to propose a novel online algorithm that can achieve zero tracking error by modeling the cost with a dynamical system. We prove the convergence of the algorithm for both strongly convex and convex problems. We further discuss the sensitivity of the proposed method to model uncertainties and quantify its performance. We discuss how the proposed algorithm can be applied to general (non-quadratic) problems using an approximate model of the cost, and analyze the convergence leveraging the small gain theorem. We present numerical results that showcase the superior performance of the proposed algorithms over previous methods for both quadratic and non-quadratic problems.
References in corpus (12)
- Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
- A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
- Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
- Online Learning with Inexact Proximal Online Gradient Descent Algorithms
- Prediction-Correction Algorithms for Time-Varying Constrained Optimization
- Timescale Separation in Autonomous Optimization
- Optimization and Learning with Information Streams: Time-varying Algorithms and Applications
- Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
- Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
- Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization
- A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
- tvopt: A Python Framework for Time-Varying Optimization