Online Optimization With Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit

• 成果类型: Article
• 署名作者: Li, Yingying; Qu, Guannan; Li, Na
• 署名单位: Harvard University; California Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3040249
• 发表日期: 2021
• 页码: 4761-4768
• 关键词: Prediction algorithms; switches; Heuristic algorithms; cost function; Task analysis; predictive models; Predictive control; online optimization; optimization; optimization algorithms; time varying systems

摘要

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.