This is the first part of a sequence of two courses on Online Optimization, focusing on basic theoretical toolkit. The second part, offered in Spring 2022, will focus on more advanced tools and applications of online optimization in operations and revenue management.
In many (almost all?) operations problems, decisions have to be made over time without perfect knowledge of future input. Portfolio are balanced periodically with uncertain stock returns; jobs have to be scheduled on servers without knowledge of future arrivals; passengers have to matched to drivers without knowledge of future demand/supply in ridesharing platforms; display ads have to be placed on webpages without knowledge of future webpage requests; items have to be priced without knowledge of demand functions; and power generation has to be committed with imperfect information about demand and solar/wind availability.
In this two-part sequence we will look at some of the models and algorithmic frameworks developed in various communities for dealing with problems involving uncertainty, and discuss some of the cutting edge research articles. The goals are t-fold:
- Develop an understanding of the strenghts and limitations of each approach. Decision making under uncertainty is an active area of research, and the hope is that by the end of the course students will gain enough maturity to start contributing to this field.
- Expose students to the rich set of mathematical techniques used: concentration inequalities, information theory, convex optimization, Linear Programming relaxation, duality, potential and work function analysis.
- Expose students to applications of online optimization in Operations Management.
Tentative list of topics for part I:
- Competitive Analysis, Potential function method.
- Primal-dual framework, Online Matching.
- Online Learning 1 -- Online Convex Optimization: Prediction with Experts; Online Mirror Descent/Online Linear Optimization; Blackwell approachability.
- Online Learning 2 -- Learning with Bandit feedback: Multi-armed Bandits (stochastic - UCB1, adversarial - EXP3, Thompson sampling); bandit linear optimization; contextual bandits.
- Secretary problems and Random order problems.
- Prophet inequalities; stochastic knapsack.