Online Optimization With Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
- 24 November 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 66 (10), 4761-4768
- https://doi.org/10.1109/tac.2020.3040249
Abstract
This article considers online optimization with a finite prediction window of cost functions and additional switching costs on the decisions. We study the fundamental limits of dynamic regret of any online algorithm for both the with-prediction and the no-prediction cases. Besides, we propose two gradient-based online algorithms: receding horizon gradient descent (RHGD) and receding horizon accelerated gradient (RHAG); and provide their regret upper bounds. RHAG's regret upper bound is close to the lower bound, indicating the tightness of our lower bound and that our RHAG is near-optimal. Finally, we conduct numerical experiments to complement the theoretical results.Keywords
Funding Information
- NSF CAREER (ECCS-1553407)
- AFOSR YIP (FA9550-18-1-0150)
- ONR YIP (N00014-19-1-2217)
This publication has 19 references indexed in Scilit:
- On convergence and performance certification of a continuous-time economic model predictive control scheme with time-varying performance indexAutomatica, 2016
- A Class of Prediction-Correction Methods for Time-Varying Convex OptimizationIEEE Transactions on Signal Processing, 2016
- Theoretical advances on Economic Model Predictive Control with time-varying costsAnnual Reviews in Control, 2016
- Non-Stationary Stochastic OptimizationOperations Research, 2015
- Curriculum learning of multiple tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Economic MPC for a Changing Economic Criterion for Linear SystemsIEEE Transactions on Automatic Control, 2014
- Online algorithms for geographical load balancingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Real-Time Nonlinear Optimization as a Generalized EquationSIAM Journal on Control and Optimization, 2010
- A Survey on Explicit Model Predictive ControlPublished by Springer Science and Business Media LLC ,2009
- Nominal stability of real-time iteration scheme for nonlinear model predictive controlIEE Proceedings - Control Theory and Applications, 2005