Werner Römisch (Humboldt University, Berlin)

Quasi-Monte Carlo methods for two-stage stochastic programs
Wednesday 22 October 2014 at 15.00, JCMB 6206

Abstract

Quasi-Monte Carlo algorithms are studied for generating scenarios to solve two-stage linear stochastic programs. 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 are quadratically integrable. This implies that randomly shifted lattice rules may achieve the optimal rate of convergence O(n-1+δ) with δ in (0,1/2] and a constant not depending on the dimension if the effective dimension is equal to two. The geometric condition is shown to be generically satisfied 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.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996