1. Distributionally Robust Optimization
The classical approach to account for uncertainty in optimization problems is to assume that the uncertain problem parameters are governed by a known probability distribution. As probability distributions must be estimated from noisy data, they are affected by estimation errors and are therefore themselves uncertain. However, estimation errors in input parameters of optimization problems can lead to biased (overly optimistic) optimization results. Moreover, the evaluation of expected values, quantiles and other probability functionals that often appear in stochastic optimization problems generally require a discretization of the underlying distribution. Commonly used discretization schemes suffer from slow convergence rates and easily render optimization problems intractable if many discretization points are included.
In our current research we employ an alternative modeling paradigm that has gained popularity due to recent advances in modern robust optimization and that describes the uncertain parameters through families of probability distributions with prescribed properties (e.g. generalized moments). This approach enables modelers to incorporate information about estimation errors into optimization problems and therefore results in a more realistic account of uncertainty. By optimizing in view of the worst-case distribution within the given family, one can mitigate the undesirable bias in the optimization results characteristic for stochastic uncertainty models. Maybe surprisingly, the resulting distributionally robust optimization problems can often be solved exactly and in polynomial time [1,2,3].
- [1] Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim. Distributionally Robust Convex Optimization. Operations Research 62(6), 1358-1376 (2014)
- [2] Steve Zymler, Daniel Kuhn, and Berç Rustem. Worst-Case Value-at-Risk of Non-Linear Portfolios. Management Science 59(1), 172-188 (2013)
- [3] Steve Zymler, Daniel Kuhn, and Berç Rustem. Distributionally Robust Joint Chance Constraints with Second-Order Moment Information. Mathematical Programming 137(1-2), 167-198 (2013)
2. Dynamic Decision Problems under Uncertainty
The crux of dynamic decision-making under uncertainty is that future decisions must be modeled as non-anticipative functions of the uncertainties. The arising functional optimization problems are therefore infinite-dimensional in nature and as such extremely difficult to handle. The classical methods for solving these problems are dynamic and stochastic programming. However, these methods suffer from a curse of dimensionality in the state dimension and the number of time periods, respectively.
In order to mitigate the inherent curse of dimensionality, we devised complexity reduction methods for uncertainty-affected dynamic decision problems with a very large (or possibly infinite) number of time periods. The key idea is to over- and underestimate the decision problem’s optimal value by perturbing the timing of data revelation. An upper (lower) bound is obtained by artificially delaying (accelerating) the inflow of new information. Moreover, a substantial complexity reduction is achieved by approximating the true continuous information flow by a sequence of isolated information shocks [1,2].
Our current research on dynamic decision-making under uncertainty is based on a new approach that has its roots in robust optimization. Instead of using a state space discretization, as is customary for the majority of classical methods, we restrict the infinite-dimensional space of all functional decisions to a finite-dimensional subspace of well-structured functions such as affine, piecewise affine or polynomial decision rules. A surprising recent result in robust optimization is that the best representatives within their respective classes of decision rules can often be computed in polynomial time. This contrasts sharply with the exponential scaling properties of classical dynamic and stochastic programming and has a profound impact on the problem sizes that can be handled in practice [3,4].
- [1] Daniel Kuhn. Aggregation and Discretization in Multistage Stochastic Programming. Mathematical Programming A 113(1), 61-94 (2008)
- [2] Daniel Kuhn. An Information-Based Approximation Scheme for Stochastic Optimization Problems in Continuous Time. Mathematics of Operations Research 34(2), 428-444 (2009)
- [3] Angelos Georghiou, Wolfram Wiesemann, and Daniel Kuhn. The Decision Rule Approach to Optimization under Uncertainty: Methodology and Applications in Operations Management. Available on Optimization Online, submitted for publication (2011)
- [4] Daniel Kuhn, Wolfram Wiesemann, and Angelos Georghiou. Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization. Mathematical Programming 130(1), 177-209 (2011)
3. Optimization of Energy Systems
Important strategic and operational decision problems of energy producers and electric utilities are naturally formulated as stochastic or robust optimization problems, e.g., unit commitment and short-term scheduling of power plants, strategic investment planning and capacity expansion of power systems and transmission networks, the construction and management of an electricity procurement portfolio under risk constraints, etc. All these decision problems are affected by uncertainties, which usually stem from the unpredictability of demand and/or prices of energy, or from the randomness of resource availability and the reliability of the transmission/generation infrastructure. Since most energy investments or operations involve irreversible decisions, a stochastic programming approach is essential.
The new modeling paradigms and solution schemes for large-scale optimization under uncertainty described in §1 and §2 have the potential to expand the range of problems in the energy sector that allow for rigorous quantitative analysis. For example, we have designed and implemented a software tool for the valuation of electricity swing options with ramping constraints and high-dimensional forward price information [1]. Moreover, we have developed a decision rule approach for energy procurement portfolio optimization problems faced by public utilities [2]. In a case study supplied by a European energy trading company, the decision rule approach has also proved highly effective for the medium-term planning of a hydropower system under uncertainty about the future electricity prices on the spot and balancing markets, water inflows and the timing of the annual snowmelt.
- [1] Gido Haarbrücker and Daniel Kuhn. Valuation of Electricity Swing Options by Multistage Stochastic Programming. Automatica 45(4), 889-899 (2009)
- [2] Paula Rocha and Daniel Kuhn. Multistage Stochastic Portfolio Optimization in Deregulated Electricity Markets Using Linear Decision Rules. European Journal of Operational Research 216(2), 397-408 (2012)