Data-driven Distributionally Robust Optimization over Time

Submission Status:under review
  • Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $ O(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.

Download full text files

Export metadata

Author:Kevin-Martin Aigner, Andreas Bärmann, Kristin Braun, Frauke Liers, Sebastian Pokutta, Oskar Schneider, Kartikey Sharma, Sebastian Tschuppik
Document Type:Preprint
Date of Publication (online):2022/07/11
Release Date:2022/07/11
Tag:distributionally robust optimization; gradient descent; learning over time
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Zuse-Institut Berlin (ZIB)
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International