Data-driven Distributionally Robust Optimization over Time

Aigner KM, Bärmann A, Braun K, Liers F, Pokutta S, Schneider O, Sharma K, Tschuppik S (2023)

Publication Language: English

Publication Status: Submitted

Publication Type: Journal article, Original article

Future Publication Type: Journal article

Publication year: 2023

Journal

INFORMS Journal on Optimization INFORMS

URI: https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/496

DOI: 10.1287/ijoo.2023.0091

Abstract

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.

Authors with CRIS profile

Kevin-Martin Aigner Professur für Optimization under Uncertainty & Data Analysis Andreas Bärmann Lehrstuhl für Analytics & Mixed-Integer Optimization Kristin Braun Lehrstuhl für Analytics & Mixed-Integer Optimization Frauke Liers-Bergmann Professur für Optimization under Uncertainty & Data Analysis Sebastian Tschuppik Professur für Optimization under Uncertainty & Data Analysis

Related research project(s)

Multi-sector coupled energy system modeling on a regional level (ESM-Regio) May 1, 2021 - April 30, 2024 Quality control by robust optimisation (SFB 1411 - D06) Design of particulate products (SFB 1411) Jan. 1, 2020 - Jan. 1, 2023 Robustification of Physics Parameters in Gas Networks (B06) (2018 - 2022) TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154) July 1, 2018 - June 30, 2022

Involved external institutions

Fraunhofer-Institut für Integrierte Schaltungen (IIS) DE Germany (DE) Georgia Institute of Technology US United States (USA) (US) Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB) DE Germany (DE)

How to cite

APA:

Aigner, K.-M., Bärmann, A., Braun, K., Liers, F., Pokutta, S., Schneider, O.,... Tschuppik, S. (2023). Data-driven Distributionally Robust Optimization over Time. INFORMS Journal on Optimization. https://dx.doi.org/10.1287/ijoo.2023.0091

MLA:

Aigner, Kevin-Martin, et al. "Data-driven Distributionally Robust Optimization over Time." INFORMS Journal on Optimization (2023).

BibTeX: Download