Quasi-Monte Carlo methods for linear two-stage stochastic programming problems
Quasi-Monte Carlo methods for linear two-stage stochastic programming problems
复制标题
DOI：
10.1007/s10107-015-0898-x
复制
发表时间：
2015-06
影响因子：
2.7
通讯作者：
H. Leövey;W. Römisch
中科院分区：
文献类型：
--
作者：
H. Leövey;W. Römisch
研究了求解两阶段线性随机规划问题的情景生成算法--拟蒙特卡罗算法。它们的被积数是分段线性二次的，但不属于QMC误差分析所考虑的函数空间。证明了在弱几何条件下，两阶段模型的方差分解项除最高阶项外均连续可微，二阶混合导数几乎处处存在，属于。这意味着，如果有效叠加维小于或等于2，则随机移位格子规则可以获得最优的收敛速度和一个不依赖于维度的常数。证明了当基本概率分布为正态分布时，几乎所有协方差矩阵都满足几何条件。我们讨论了降维的有效方法和降维技巧。对具有正常输入的生产计划模型的数值实验表明，当使用随机移位的格子规则或置乱的Sobol点集结合主成分分析进行降维时，确实获得了接近最优收敛速度的收敛速度。
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 convergencewithand 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.