Logo of Humboldt-Universität zu BerlinLogo of Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Header image: facade of Humboldt-Universität zu Berlin
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2012
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2012
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2012
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2012
  • View Item
2012-03-19Buch DOI: 10.18452/8423
Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
Sen, Suvrajeet
Zhou, Zhihong
Multi-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.
Files in this item
Thumbnail
3.pdf — Adobe PDF — 296.4 Kb
MD5: 348a56fa158226345c5062886594f220
Cite
BibTeX
EndNote
RIS
InCopyright
Details
DINI-Zertifikat 2019OpenAIRE validatedORCID Consortium
Imprint Policy Contact Data Privacy Statement
A service of University Library and Computer and Media Service
© Humboldt-Universität zu Berlin
 
DOI
10.18452/8423
Permanent URL
https://doi.org/10.18452/8423
HTML
<a href="https://doi.org/10.18452/8423">https://doi.org/10.18452/8423</a>