TY - JOUR
T1 - Online Optimization with Predictions and Switching Costs
T2 - Fast Algorithms and the Fundamental Limit
AU - Li, Yingying
AU - Qu, Guannan
AU - Li, Na
N1 - Funding Information:
Manuscript received August 21, 2020; accepted October 28, 2020. Date of publication November 24, 2020; date of current version September 27, 2021. This work was supported in part by NSF CAREER grant under Grant ECCS-1553407 , in part by AFOSR YIP under Grant FA9550-18-1-0150, and in part by ONR YIP under Grant N00014-19-1-2217. Recommended by Associate Editor S. Grammatico. (Corresponding author: Yingying Li.) Yingying Li and Na Li are with the John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138 USA (e-mail: [email protected]; [email protected]).
Publisher Copyright:
© 2021 IEEE.
PY - 2021/10
Y1 - 2021/10
N2 - 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.
AB - 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.
KW - Online optimization
KW - optimization
KW - optimization algorithms
KW - time varying systems
UR - http://www.scopus.com/inward/record.url?scp=85097197759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097197759&partnerID=8YFLogxK
U2 - 10.1109/TAC.2020.3040249
DO - 10.1109/TAC.2020.3040249
M3 - Article
AN - SCOPUS:85097197759
SN - 0018-9286
VL - 66
SP - 4761
EP - 4768
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 10
ER -