PhD Thesis Defense: Russell Lee, Learning-Augmented Online Algorithms for Energy Optimization

Content

Speaker

Russell Lee

Abstract

For competitive analysis of online algorithms, an online algorithm only knows current and past inputs and must make decisions sequentially as inputs arrive.  The primary performance metric of competitive ratio - the maximum ratio of the online algorithm’s performance against the optimal offline algorithm’s performance with full knowledge of future inputs - is calculated over all possible problem instances. This framework is highly suited for energy optimization problems that face uncertainties in future variables such as price fluctuation, electricity demand, and renewable energy generation. Online algorithms are then able to provide theoretical performance guarantees on the cost of procuring energy, even when facing worst-case outcomes for future inputs. In this proposal, we present optimal online algorithms for energy optimization in the competitive analysis setting. First, we consider online linear optimization with inventory management constraints where the clearing price of electricity is determined by bids submitted by market participants. We propose algorithms where the competitive ratio approaches those of optimal online algorithms in the basic setting without bids.

Competitive analysis fares well when future inputs are adversarial, but in practice, predictions on future inputs are available through machine learning or other predictive models.  This has sparked a growing area of research on learning-augmented online algorithms that are able to use predictions while maintaining provable performance guarantees.  This setting is well suited to the nature of predictions in energy optimization problems, where data-driven models for price and demand can leverage some degree of seasonality. However, underlying factors such as weather and renewable generation variation still cause unpredictable spikes in price and demand. We then present energy optimization problems in the learning-augmented setting. First, we analyze the peak-aware energy scheduling problem and propose Pareto-optimal algorithms that can utilize a trust parameter of the predictions. Next, we consider online search problems with predictions. We design our algorithm with both robustness (when prediction error is arbitrary) and consistency (when predictions are accurate) guarantees such that our algorithm achieves the Pareto-optimal tradeoff of robustness and consistency. In real-world applications of online search problems, factors such as peak energy cost or inventory usage require adjust algorithm design for competitive analysis. We consider extensions of these learning-augmented algorithms with applications to energy procurement, such as the storage-assisted and inventory cost aware settings.

Advisor

Mohammad Hajiesmaili