UC Berkeley

Decision-makers often face environments which vary over time and deal with uncertainty as a result. Problems with temporal variation differ based on how frequently they are solved and what information about the present or future is available to the decision-maker; each class of problem poses distinct challenges and requires tailored solutions. In this dissertation, we design and analyze methods to support decision-makers in these settings, with an emphasis on applications in electric power systems.

Online optimization, in which a player makes a sequence of decisions aimed at minimizing the damage inflicted by their adversary, is the first class of problems considered. Here, we shed light on online nonconvex optimization problems in which algorithms are evaluated against the optimal decision at each time using the notion of dynamic regret. The adversary's loss functions are arbitrarily nonconvex but have global solutions that are slowly time-varying. To address this problem we first analyze the region around the global solutions to define time-varying target sets. Then, we introduce two algorithms and prove that the dynamic regret for each algorithm is bounded by a function of the temporal variation in the optimal decision. The first algorithm assumes the decision-maker has some prior knowledge about the initial loss function. The second algorithm makes no assumption about prior knowledge, and instead it relies on random sampling and memory to find and then track the target sets over time. In this case, the landscape of the loss functions determines the likelihood that the dynamic regret will be small. Numerical experiments validate these theoretical results and highlight the impact of a single low-complexity problem early in the sequence.

Time-varying optimization, in which a series of linked problems are solved sequentially using information about past decisions, but not considering the future, is the second class of problems considered. Specifically, we analyze the optimality behavior of solution trajectories for optimal power flow (OPF) with time-varying load. Despite its nonlinearity, time-varying OPF is commonly solved every 5-15 minutes using local-search algorithms. Failing to obtain the globally optimal solution of power optimization problems jeopardizes the grid’s reliability and causes poor financial and environmental outcomes. An empirical study on California data shows that, with enough variation in the data, local search methods can solve OPF to global optimality, even if the problem has many local minima. To explain this phenomenon, we introduce a backward mapping that relates the time-varying OPF’s global solution at a given time to a set of desirable initial points. We show that this mapping could act as a stochastic gradient ascent algorithm on an implicitly convexified formulation of OPF, justifying the escape of poor solutions over time. This work is the first to mathematically explain how temporal data variation affects the complexity of solving power operational problems.

Multi-period optimization under uncertainty, in which decisions for the entire time horizon are made at once, is the third and final class of problems considered. Within this class, we focus on the decision-making problem facing hybrid power plant operators when participating in wholesale electricity markets with the goal of enabling researchers to accurately incorporate these resources into simulations of future electricity systems. To this end, a stochastic optimization model is developed to maximize the revenue of the plant, which consists of a renewable generator and an energy storage resource that appear as a single, combined unit to the market, while limiting risk due to uncertainty in market prices and generation levels, through price-quantity bid curves. The uncertainty is represented by scenarios, and a detailed methodology is provided for creating scenarios which both reflect the type of information a hybrid operator would have and only require the limited data which is available in simulation settings. This work advances existing models by allowing greater cooperation between the generator and storage components while also enforcing market limits on bid curves' complexity. Further, the approach ensures economically-sound behavior even when faced with unforeseen events.