Optimization Online


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

Holger Heitsch (heitsch***at***math.hu-berlin.de)
Hernan Leovey (leovey***at***math.hu-berlin.de)
Werner Romisch (romisch***at***math.hu-berlin.de)

Abstract: 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 lie in the function spaces considered for QMC error analysis. 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. Hence, Quasi-Monte Carlo algorithms may achieve the optimal rate of convergence O(n^(-1+Delta)) with Delta in (0,1/2] and a constant not depending on the dimension. The geometric condition is shown to be generically satisfied if the underlying distribution is normal. We discuss sensitivity indices, effective dimensions and dimension reduction techniques for two-stage integrands. Numerical experiments show that indeed convergence rates close to the optimal rate are achieved when using randomly scrambled Sobol' point sets and randomly shifted lattice rules accompanied with suitable dimension reduction techniques.

Keywords: stochastic programs, two-stage, scenario approximation, quasi-Monte Carlo, ANOVA

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 09/25/2012
Entry Accepted: 09/25/2012
Entry Last Modified: 01/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society