Princeton University

School of Engineering & Applied Science

Local Approximation and Hierarchical Methods for Stochastic Optimatization

Harvey Cheng
Engineering Quadrangle, J401
Thursday, May 18, 2017 - 2:00pm to 4:30pm

Stochastic optimization, also known as optimization under uncertainty, has a diverse set of applications in today’s world, such as renewable energy, finance, logistics, and artificial intelligence. As the problems become increasingly complicated (larger scales and more stochastic parameters), solving these problems become computationally intractable; this is the well-known curse of dimensionality. In this thesis, we present local and hierarchical approximation methods for two classes of stochastic optimization problems: optimal learning and Markov decision processes, to circumvent the curse of dimensionality.
In the first part of the thesis, we introduce an optimal learning policy that uses locally linear model estimating the posterior mean of the unknown objective function. The method uses a compact representation of the function which avoids storing the entire history, as is typically required by nonparametric methods. We show the policy is asymptotically optimal in theory, and experimental works suggests that the method can reliably find the optimal solution on a range of test functions.
In the second part of the thesis, we are motivated by an application where we want to co-optimize a grid-level battery for multiple revenue: energy arbitrage and frequency regulation. The nature of this problem requires the battery to make charging and discharging decisions at different time scales while accounting for the stochastic information such as load demand, electricity prices, and regulation signals. We propose two methods to circumvent the computation bottleneck of this problem. First, we propose a nested model that structure the co-optimization problem into smaller sub-problems with reduced state space. This new model allows us to understand how the battery behaves down to the two-second dynamics (that of the frequency regulation market). Second, we introduce a sample-based method to approximate entire value function using low-rank matrix completion. We test these methods on historical price data from the PJM Interconnect and show that it outperforms the baseline approach used in the industry.