Online Convex Optimization and Predictive Control in Dynamic Environments

Citation

Sun, Haoyuan (2021) Online Convex Optimization and Predictive Control in Dynamic Environments. Senior thesis (Major), California Institute of Technology. doi:10.7907/b6sh-vs59. https://resolver.caltech.edu/CaltechTHESIS:06222021-044112185

Abstract

We study the performance of an online learner under a framework in which it receives partial information from a dynamic, and potentially adversarial, environment at discrete time steps. The goal of this learner is to minimize the sum of costs incurred at each time step and its performance is compared against an offline learner with perfect information of the environment.

We are interested in the scenarios where, in addition to some costs at each time step, there are some penalties or constraints on the learner's successive decisions. In the first part of this thesis, we investigate a Smoothed Online Convex Optimization (SOCO) setting where the cost functions are strongly convex and the learner pays a squared ℓ₂ movement cost for changing decision between time steps. We shall present a lower bound on the competitive ratio of any online learner in this setting and show a series of algorithmic ideas that lead to an optimal algorithm matching this lower bound. And in the second part of this thesis, we investigate a predictive control problem where the costs are well-conditioned and the learner's decisions are constrained by a linear time-varying (LTV) dynamics but has exact prediction on the dynamics, costs and disturbances for the next k time steps. We shall discuss a novel reduction from this LTV control problem to the aforementioned SOCO problem and use this to achieve a dynamic regret of O(λ^kT) and a competitive ratio of 1 + O(λ^k) for some positive constant λ < 1.

Thesis Files