A stability result for linear Markovian stochastic optimization problems
- PDF / 643,361 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 186 Views
Series A
A stability result for linear Markovian stochastic optimization problems Adriana Kiszka1 · David Wozabal1 Received: 2 July 2018 / Accepted: 25 September 2020 © The Author(s) 2020
Abstract In this paper, we propose a semi-metric for Markov processes that allows to bound optimal values of linear Markovian stochastic optimization problems. Similar to existing notions of distance for general stochastic processes, our distance is based on transportation metrics. As opposed to the extant literature, the proposed distance is problem specific, i.e., dependent on the data of the problem whose objective value we want to bound. As a result, we are able to consider problems with randomness in the constraints as well as in the objective function and therefore relax an assumption in the extant literature. We derive several properties of the proposed semi-metric and demonstrate its use in a stylized numerical example. Keywords Stochastic optimization · Wasserstein distance · Scenario lattices Mathematics Subject Classification 90C15 · 90C31 · 90C40 · 60J05
1 Introduction Stochastic optimization is concerned with the solution of optimization problems that involve random quantities as data. Consequently, the decisions x(ξ ) depend on values of a random process ξ , making stochastic optimization a problem in function spaces. Mirroring the situation in deterministic optimization, only few stochastic optimization problems lend itself to analytical treatment and allow for closed form solutions. In the following, we therefore focus on discrete time problems that are solved numerically. The theory of stochastic optimization as well as the development of solution methods made great advances in the last decades. In particular, there exists a sound theory
B
David Wozabal [email protected] Adriana Kiszka [email protected]
1
School of Management, Technical University of Munich, Arcisstraße 21, 80333 Munich, Germany
123
A. Kiszka, D. Wozabal
for two-stage stochastic optimization problems, i.e., problems with only one decision stage in the future (see [7,53] for an overview). Consequently, two-stage stochastic optimization is nowadays routinely applied by researchers and industry practitioners alike. State-of-the-art methods are based on discrete representations of the, possibly continuous, source of randomness in the form of a finite set of samples or scenarios. This can either be achieved by sample average approaches (see [53] for an introduction) or by explicitly choosing representative scenarios. In this paper, we will focus on the latter. Despite the abovementioned successes, it became clear quite early that the effort required to solve stochastic optimization does not scale well in the problem’s size. More specifically, it has been shown that stochastic optimization problems exhibit non-polynomial increase in complexity as the number of random variables increases [21]. The problem underlying these difficulties is the numerical evaluation of high dimensional integrals, which is in turn related to the problem of o
Data Loading...
