A Caltech Library Service

Online Convex Optimization and Predictive Control in Dynamic Environments


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


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.

Item Type:Thesis (Senior thesis (Major))
Subject Keywords:online convex optimization, linear time-varying systems
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Wierman, Adam
Thesis Committee:
  • None, None
Defense Date:2021
Record Number:CaltechTHESIS:06222021-044112185
Persistent URL:
Sun, Haoyuan0000-0002-6203-0198
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14281
Deposited By: Haoyuan Sun
Deposited On:28 Jun 2021 21:11
Last Modified:28 Jun 2021 21:12

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page