Quasi-Monte Carlo methods for linear two-stage stochastic programming problems

• 成果类型: Article; Proceedings Paper
• 署名作者: Leovey, H.; Roemisch, W.
• 署名单位: Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0898-x
• 发表日期: 2015
• 页码: 315-345
• 关键词: high-dimensional integration; smooth functions; lattice rules; variance; CONVERGENCE; algorithms

摘要

Quasi-Monte Carlo (QMC) algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to 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 continuously differentiable and second order mixed derivatives exist almost everywhere and belong to . This implies that randomly shifted lattice rules may achieve the optimal rate of convergence with and a constant not depending on the dimension if the effective superposition dimension is less than or equal to two. The geometric condition is shown to be satisfied for almost all covariance matrices if the underlying probability distribution is normal. We discuss effective dimensions and techniques for dimension reduction. Numerical experiments for a production planning model with normal inputs show that indeed convergence rates close to the optimal rate are achieved when using randomly shifted lattice rules or scrambled Sobol' point sets accompanied with principal component analysis for dimension reduction.