A framework for a class of online convex optimization problems with uncertain objective

We study a class of convex online optimization problems where the cost functions for each stage are uncertain. In particular, we consider the case where for each stage, a decision must be made after the cost function has been revealed. Such optimization problems arise, for example, in energy management for smart grids, where decisions regarding the energy consumption of devices are made based on real-time energy usage measurements. Several paradigms for optimization under uncertainty exist, such as stochastic programming and robust optimization. However, these approaches are less suitable for online optimization in smart grids. One reason for this is that, on the one hand, the resulting reformulated problems are often very large but, on the other hand, must be solved on embedded systems with relatively low computation power. Another reason is that these approaches require quantitative knowledge of the uncertain data, for example the underlying distribution (stochastic programming) or an uncertainty set (robust optimization). This is difficult for energy usage since we require information of individual households on a small time scale (e.g., 15 minutes), which is equivalent to predicting human behavior.

We present a framework the considered class of online convex optimization problems that overcomes the above disadvantages. The key observation in the framework is that we can characterize the optimal solution at a given stage using the optimal Lagrange multipliers and parameters corresponding to the current stage. In particular, we do not require any information on the cost functions of future stages, i.e., we do not need to predict any of these functions and their underlying data. Instead, our approach requires only a prediction of the optimal Lagrange multipliers as input. The resulting approach is robust against prediction errors, which we demonstrate by deriving a bound on the difference between the online and offline (optimal) objective value that holds for a wide subclass of problem instances. Moreover, the problems that have to be solved at each stage are not larger or more difficult than the original deterministic optimization problem, which makes the approach suitable for applications where computational power is limited. We demonstrate the effectiveness of the framework by applying it to the problem of scheduling the charging of multiple electric vehicles while minimizing peak consumption.

Bio:

Martijn is a PhD student within the EEMCS faculty of the University of Twente, the Netherlands. His research focuses on optimization algorithms for planning problems in decentralized energy systems. In particular, he studies the influence of data uncertainty in these problems and algorithms that are robust against this uncertainty.

Registration to Krzysztof Postek, postek@ese.eur.nl  is required for availability of lunch.