• search hit 161 of 1103
Back to Result List

Are Quasi-Monte Carlo algorithms efficient for two-stage stochastic programs ?

Please always quote using this URN:urn:nbn:de:0296-matheon-11402
  • Quasi-Monte Carlo algorithms are studied for designing discrete approximations of two-stage linear stochastic programs. Their integrands are piecewise linear, but neither smooth nor of bounded variation in the sense of Hardy and Krause. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are smooth and, hence, certain Quasi-Monte Carlo algorithms may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta\in(0,\frac{1}{2})$ and a constant not depending on the dimension if the integrands belong to weighted tensor product Sobolev spaces with properly selected weights. The geometric condition is generically (i.e., almost everywhere) satisfied if the underlying distribution is normal. We also discuss sensitivity indices and efficient dimensions of two-stage integrands, and suggest a dimension reduction heuristic for such integrands.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Holger Heitsch, Werner Roemisch
URN:urn:nbn:de:0296-matheon-11402
Referee:Fredi Tröltzsch
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/06/06
Release Date:2012/06/06
Tag:ANOVA decomposition; Quasi-Monte Carlo; efficient dimension; scenario; stochastic programming; two-stage
Institute:Humboldt-Universität zu Berlin
MSC-Classification:00-XX GENERAL / 00-02 Research exposition (monographs, survey articles)
Preprint Number:964
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.