Zum Inhalt springen

Mathematisches Kolloquium TU Darmstadt

Andere Veranstaltungen

Sample average approximation and randomization

Datum: 25.01.2023

Zeit: 17:15–18:15 Uhr

We consider the single-stage stochastic optimization problem to minimize
the expected cost over a set of decisions. Motivated by the dual
formulation of optimal stopping problems we focus on the following
situation: The set of minimizers is infinite and there is at least one
"surely optimal" decision, i.e., a minimizer whose cost has zero
  A classical method for solving stochastic optimization problems
numerically is sample average approximation (SAA), a Monte Carlo method
which replaces the expectation by the empirical mean over a simulated
sample and then applies deterministic algorithms to search for a
minimizer of the approximate problem. While SAA is known to converge to
an optimal decision under appropriate assumptions, we illustrate that it
may fail to converge to a surely optimal decision.
  In order to exploit the zero-variance property of surely optimal
decisions we suggest a randomization of the original optimization
problem, which enforces convergence of SAA to surely optimal decisions,
while preserving the structure of the problem (e.g., convexity or linear
programming formulation of the deterministic problem). We state improved
convergence properties of the randomization approach in the framework of
optimal stopping and illustrate the results in some numerical


Christian Bender, Universität des Saarlandes


TU Darmstadt, S2|08 171 (Uhrturm-Hörsaal)
Hochschulstraße 4, 64289 Darmstadt


Technische Universität Darmstadt

Fachbereich Mathematik - Stochastik
Schlossgartenstraße 7
64289 Darmstadt
Telefon: +49 6151 16-23380
Telefax: +49 6151 16-23381


Goethe-Universität Frankfurt am Main, Johannes Gutenberg-Universität Mainz

Für diese Veranstaltung ist keine Anmeldung erforderlich. PDF- Link