QMC methods for stochastic programs: ANOVA decomposition of integrands

Abstract We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying that first and higher order terms of the integrand’s ANOVA decomposition (Math. Comp. 79 (2010), 953–966) have mixed weak first order partial derivatives. This leads to a good smooth approximation of the integrand and, hence, to good convergence rates of randomized QMC methods if the effective (superposition) dimension is low.Abstract We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying that first and higher order terms of the integrand’s ANOVA decomposition (Math. Comp. 79 (2010), 953–966) have mixed weak first order partial derivatives. This leads to a good smooth approximation of the integrand and, hence, to good convergence rates of randomized QMC methods if the effective (superposition) dimension is low.

Mathematical ProgrammingJul 14, 20201 citation

A Practical Approach to the Error Estimation of Quasi-Monte Carlo Integrations

Hozumi Morohosi, Masanori Fushimi

Springer eBooksJan 1, 200021 citations

Error reduction techniques in quasi-monte carlo integration

Giray Ökten

Mathematical and Computer ModellingOct 1, 199917 citations

Effective Dimension of Some Weighted Pre-Sobolev Spaces with Dominating Mixed Partial Derivatives

Art B. Owen

This paper considers two notions of effective dimension for quadrature in weighted pre-Sobolev spaces with dominating mixed partial derivatives. We begin by finding a ball in those spaces just barely large enough to contain a function with unit variance. If no function in that ball has more than $\varepsilon$ of its variance from analysis of variance (ANOVA) components involving interactions of order $s$ or more, then the space has effective dimension at most $s$ in the superposition sense. A similar truncation sense notion replaces the cardinality of an ANOVA component by the largest index it contains. These effective dimension definitions for the integration problem coincide with some of the definitions in information-based complexity for the function approximation problem. Some Poincaré-type inequalities are used to bound variance components by multiples of these space's squared norm and those in turn provide bounds on effective dimension. Very low effective dimension in the superposition sense holds for some spaces defined by product weights in which quadrature is strongly tractable. The superposition dimension is $O( \log(1/\varepsilon)/\log(\log(1/\varepsilon)))$ just like the superposition dimension used in the multivariate decomposition method. Surprisingly, even spaces where all subset weights are equal, regardless of their cardinality or included indices, have low superposition dimension in this sense. This paper does not require periodicity of the integrands.This paper considers two notions of effective dimension for quadrature in weighted pre-Sobolev spaces with dominating mixed partial derivatives. We begin by finding a ball in those spaces just barely large enough to contain a function with unit variance. If no function in that ball has more than $\varepsilon$ of its variance from analysis of variance (ANOVA) components involving interactions of order $s$ or more, then the space has effective dimension at most $s$ in the superposition sense. A similar truncation sense notion replaces the cardinality of an ANOVA component by the largest index it contains. These effective dimension definitions for the integration problem coincide with some of the definitions in information-based complexity for the function approximation problem. Some Poincaré-type inequalities are used to bound variance components by multiples of these space's squared norm and those in turn provide bounds on effective dimension. Very low effective dimension in the superposition sense holds for some spaces defined by product weights in which quadrature is strongly tractable. The superposition dimension is $O( \log(1/\varepsilon)/\log(\log(1/\varepsilon)))$ just like the superposition dimension used in the multivariate decomposition method. Surprisingly, even spaces where all subset weights are equal, regardless of their cardinality or included indices, have low superposition dimension in this sense. This paper does not require periodicity of the integrands.

arXiv:1709.06695SIAM Journal on Numerical AnalysisJan 1, 201912 citations

American option pricing with randomized quasi-Monte Carlo simulations

Maxime Dion, Pierre L’Ecuyer

We study the pricing of American options using least-squares Monte Carlo combined with randomized quasi-Monte Carlo (RQMC), viewed as a variance reduction method. We find that RQMC reduces both the variance and the bias of the option price obtained in an out-of-sample evaluation of the retained policy, and improves the quality of the returned policy on average. Various sampling methods of the underlying stochastic processes are compared and the variance reduction is analyzed in terms of a functional ANOVA decomposition.We study the pricing of American options using least-squares Monte Carlo combined with randomized quasi-Monte Carlo (RQMC), viewed as a variance reduction method. We find that RQMC reduces both the variance and the bias of the option price obtained in an out-of-sample evaluation of the retained policy, and improves the quality of the returned policy on average. Various sampling methods of the underlying stochastic processes are compared and the variance reduction is analyzed in terms of a functional ANOVA decomposition.

Winter Simulation ConferenceDec 1, 201017 citations

\varepsilon

of its variance from analysis of variance (ANOVA) components involving interactions of order

s

or more, then the space has effective dimension at most

s

in the superposition sense. A similar truncation sense notion replaces the cardinality of an ANOVA component by the largest index it contains. These effective dimension definitions for the integration problem coincide with some of the definitions in information-based complexity for the function approximation problem. Some Poincaré-type inequalities are used to bound variance components by multiples of these space's squared norm and those in turn provide bounds on effective dimension. Very low effective dimension in the superposition sense holds for some spaces defined by product weights in which quadrature is strongly tractable. The superposition dimension is

O( \log(1/\varepsilon)/\log(\log(1/\varepsilon)))

just like the superposition dimension used in the multivariate decomposition method. Surprisingly, even spaces where all subset weights are equal, regardless of their cardinality or included indices, have low superposition dimension in this sense. This paper does not require periodicity of the integrands.