Show simple item record

2012-03-19Buch DOI: 10.18452/8423
Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
dc.contributor.authorSen, Suvrajeet
dc.contributor.authorZhou, Zhihong
dc.contributor.editorHigle, Julie L.
dc.contributor.editorRömisch, Werner
dc.contributor.editorSen, Surrajeet
dc.date.accessioned2017-06-16T20:26:34Z
dc.date.available2017-06-16T20:26:34Z
dc.date.created2012-03-19
dc.date.issued2012-03-19
dc.date.submitted2012-03-13
dc.identifier.urihttp://edoc.hu-berlin.de/18452/9075
dc.description.abstractMulti-stage stochastic programs (MSP) pose some of the more challenging optimizationproblems. Because such models can become rather intractable in general, it is important todesign algorithms that can provide approximations which, in the long run, yield solutions that arearbitrarily close to an optimum. In this paper, we propose a statistically motivated sequentialsampling method that is applicable to multi-stage stochastic linear programs, and we refer to it asthe multistage stochastic decomposition (MSD) algorithm. As with earlier SD methods for two-stage stochastic linear programs, this approach preserves one of the most attractive features ofSD: asymptotic convergence of the solutions can be proven (with probability one) without anyiteration requiring more than a small sample-size. This data-driven approach also allows us tosequentially update value function approximations, and the computations themselves can beorganized in a manner that decomposes the scenario generation (stochastic) process from theoptimization computations. As a by-product of this study, we also show that SD algorithms areessentially approximate dynamic programming algorithms for SP. Our asymptotic analysis alsoreveals conceptual connections between multiple SP algorithms.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectmulti-stage stochastic programmingeng
dc.subjectsequential samplingeng
dc.subjectstochastic decompositioneng
dc.subjectapproximate dynamic programmingeng
dc.subject.ddc510 Mathematik
dc.titleMultistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-100200569
dc.identifier.doihttp://dx.doi.org/10.18452/8423
local.edoc.container-titleStochastic Programming E-Print Series
local.edoc.pages21
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-volume2012
local.edoc.container-issue3
local.edoc.container-erstkatid2936317-2

Show simple item record