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.
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 |