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 which 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. Second, we introduce the peak-aware one way trading problem. In the basic one way trading problem that was proposed more than two decades ago, a player must minimize the cost of buying a fixed quantity of an asset from a market with unknown price fluctuation. In the new variant, we consider a peak cost based on the maximum amount traded in a single time slot. This problem is more challenging than the basic version since it comes with a new long-term coupled term in the objective function. We propose a new online algorithm in the more general peak-aware setting which applies a dynamic peak utilization and can match the competitive ratio of the basic setting.
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 are able to leverage some degree of seasonality. However, underlying factors such as weather variation still cause unpredictable spikes in price and demand.
We then present energy optimization problems in the learning-augmented setting. First, we extend the one way trading problem to the more general k-min search problem 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. Second, we analyze the peak-aware energy scheduling problem and propose Pareto-optimal algorithms that can utilize a trust parameter of the predictions.
Advisor: Mohammad Hajiesmaili