When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε^−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε^−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.     

Intractability Results for Positive Quadrature Formulas and Extremal Problems for Trigonometric Polynomials

Lower bounds for the error of quadrature formulas with positive weights are proved. We get intractability results for quasi-Monte Carlo methods and, more generally, for positive formulas. We consider general classes of functions but concentrate on lower bounds for relatively small classes of trigonometric polynomials. We also conjecture that similar lower bounds hold for arbitrary quadrature formulas and state different equivalent conjectures concerning positive definiteness of certain matrices and certain extremal problems for trigonometric polynomials. We also study classes of functions with weighted norms where some variables are “more important” than others. Positive quadrature formulas are then tractable iff the sum of the weights is bounded.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

A Constructive Approach to Strong Tractability Using Quasi-Monte Carlo Algorithms

We prove in a constructive way that multivariate integration in appropriate weighted Sobolev classes is strongly tractable and the ε-exponent of strong tractability is 1 (which is the best-possible value) under a stronger assumption than Sloan and Woźniakowski's assumption. We show that quasi-Monte Carlo algorithms based on the Sobol sequence and Halton sequence achieve the convergence order O(n^−1+δ) for any δ>0 independent of the dimension with a worst-case deterministic guarantee (where n is the number of function evaluations). This implies that quasi-Monte Carlo algorithms based on the Sobol and Halton sequences converge faster and therefore are superior to Monte Carlo methods independent of the dimension for integrands in suitable weighted Sobolev classes.     

Liberating the weights

A partial answer to why quasi-Monte Carlo (QMC) algorithms work well for multivariate integration was given in Sloan and Woźniakowski (J. Complexity 14 (1998) 1–33) by introducing weighted spaces. In these spaces the importance of successive coordinate directions is quantified by a sequence of weights. However, to be able to make use of weighted spaces for a particular application one has to make a choice of the weights.In this work, we take a more general view of the weights by allowing them to depend arbitrarily not only on the coordinates but also on the number of variables. Liberating the weights in this way allows us to give a recommendation for how to choose the weights in practice. This recommendation results from choosing the weights so as to minimize the error bound. We also consider how best to choose the underlying weighted Sobolev space within which to carry out the analysis.We revisit also lower bounds on the worst-case error, which change in many minor ways now, since the weights are allowed to depend on the number of variables, and we do not assume that the weights are uniformly bounded as has been assumed in previous papers. Necessary and sufficient conditions for QMC tractability and strong QMC tractability are obtained for the weighted Sobolev spaces with general weights.In the final section, we show that the analysis of variance decomposition of functions from one of the Sobolev spaces is equivalent to the decomposition of functions with respect to an orthogonal decomposition of this space.     

New star discrepancy bounds for (t,m,s)-nets and (t,s)-sequences

In this paper, we derive new general upper bounds on the star discrepancy of $(t,m,s)$ -nets and $(t,s)$ -sequences. These kinds of point sets are among the most widely used in quasi-Monte Carlo methods for numerical integration. By our new results, we improve on previous discrepancy bounds and prove a conjecture stated by the second author in an earlier paper.     

Approximation by radial basis functions with finitely many centers

Interpolation by translates of “radial” basis functions Φ is optimal in the sense that it minimizes the pointwise error functional among all comparable quasiinterpolants on a certain “native” space of functions $\mathcal{F}_\Phi $ . Since these spaces are rather small for cases where Φ is smooth, we study the behavior of interpolants on larger spaces of the form $\mathcal{F}_{\Phi _0 } $ for less smooth functions Φ₀. It turns out that interpolation by translates of Φ to mollifications of functionsf from $\mathcal{F}_{\Phi _0 } $ yields approximations tof that attain the same asymptotic error bounds as (optimal) interpolation off by translates of Φ₀ on $\mathcal{F}_{\Phi _0 } $ .     

Revisiting several problems and algorithms in continuous location with \ell _\tau norms

This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different \(\ell _\tau \) norms, \(\tau \ge 1\) , in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous \(\ell _\tau \) ordered median location problems Nickel and Puerto (Facility location: a unified approach, 2005) in dimension \(d\) (including of course the \(\ell _\tau \) minisum or Fermat-Weber location problem for any \(\tau \ge 1\) ). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.     

The Brownian Bridge Does Not Offer a Consistent Advantage in Quasi-Monte Carlo Integration

The Brownian bridge has been suggested as an effective method for reducing the quasi-Monte Carlo error for problems in finance. We give an example of a digital option where the Brownian bridge performs worse than the standard discretization. Hence, the Brownian bridge does not offer a consistent advantage in quasi-Monte Carlo integration. We consider integrals of functions of d variables with Gaussian weights such as the ones encountered in the valuation of financial derivatives and in risk management. Under weak assumptions on the class of functions, we study quasi-Monte Carlo methods that are based on different covariance matrix decompositions. We show that different covariance matrix decompositions lead to the same worst case quasi-Monte Carlo error and are, therefore, equivalent.     

On the L p discrepancy of two-dimensional folded Hammersley point sets

We give an explicit construction of two-dimensional point sets whose L _p discrepancy is of best possible order for all \({1 \le p \le \infty}\) . It is provided by folding Hammersley point sets in base b by means of the b-adic baker’s transformation which has been introduced by Hickernell (Monte Carlo and quasi-Monte Carlo methods. Springer, Berlin, 274–289, 2002) for b =  2 and Goda, Suzuki, and Yoshiki (The b-adic baker’s transformation for quasi-Monte Carlo integration using digital nets. arXiv:1312.5850 [math:NA], 2013) for arbitrary \({b \in \mathbb{N}}\) , \({b \ge 2}\) . We prove that both the minimum Niederreiter–Rosenbloom–Tsfasman weight and the minimum Dick weight of folded Hammersley point sets are large enough to achieve the best possible order of L _p discrepancy for all \({1 \le p \le \infty}\) .     

Error bounds for quasi-Monte Carlo integration with uniform point sets

We establish new error bounds for quasi-Monte Carlo integration for node sets with a special kind of uniformity property. The methods of proving these error bounds work for arbitrary probability spaces. Only the bounds in terms of the modulus of continuity of the integrand require also the structure of a metric space.     

Approximation of \bar \psi - integrals of periodic functions by Fourier sums (small smoothness). Iof periodic functions by Fourier sums (small smoothness). I

We investigate the rate of convergence of Fourier series on the classes $L^{\bar \psi } $ N in the uniform and integral metrics. The results obtained are extended to the case where the classes $L^{\bar \psi } $ N are the classes of convolutions of functions from N with kernels with slowly decreasing coefficients. In particular, we obtain asymptotic equalities for the upper bounds of deviations of the Fourier sums on the sets $L^{\bar \psi } $ N which are solutions of the Kolmogorov-Nikol’skii problem. In addition, we establish an analog of the well-known Lebesgue inequality.     

On the complexity of parabolic initial-value problems with variable drift

We study the intrinsic difficulty of solving linear parabolic initial-value problems numerically at a single point. We present a worst-case analysis for deterministic as well as for randomized (or Monte Carlo) algorithms, assuming that the drift coefficients and the potential vary in given function spaces. We use fundamental solutions (parametrix method) for equations with unbounded coefficients to relate the initial-value problem to multivariate integration and weighted approximation problems. Hereby we derive lower and upper bounds for the minimal errors. The upper bounds are achieved by algorithms that use Smolyak formulas and, in the randomized case, variance reduction. We apply our general results to equations with coefficients from Hölder classes, and here, in many cases, the upper and lower bounds almost coincide and our algorithms are almost optimal.     

Approximation of \bar \psi - Integrals of periodic functions by Fourier sums (small smoothness). IIof periodic functions by Fourier sums (small smoothness). II

We investigate the rate of convergence of Fourier series on the classes $L^{\bar \psi } $ N in the uniform and integral metrics. The results obtained are extended to the case where the classes $L^{\bar \psi } $ N are the classes of convolutions of functions from ? with kernels with slowly decreasing coefficients. In particular, we obtain asymptotic equalities for the upper bounds of deviations of the Fourier sums on the sets $L^{\bar \psi } $ N, which are solutions of the Kolmogorov-Nikol’skii problem. In addition, we establish an analog of the well-known Lebesgue inequality.     

Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients

We consider the application of multilevel Monte Carlo methods to elliptic PDEs with random coefficients. We focus on models of the random coefficient that lack uniform ellipticity and boundedness with respect to the random parameter, and that only have limited spatial regularity. We extend the finite element error analysis for this type of equation, carried out in Charrier et al. (SIAM J Numer Anal, 2013), to more difficult problems, posed on non-smooth domains and with discontinuities in the coefficient. For this wider class of model problem, we prove convergence of the multilevel Monte Carlo algorithm for estimating any bounded, linear functional and any continuously Fréchet differentiable non-linear functional of the solution. We further improve the performance of the multilevel estimator by introducing level dependent truncations of the Karhunen–Loève expansion of the random coefficient. Numerical results complete the paper.     

Convergence analysis of high-order time-splitting pseudo-spectral methods for rotational Gross–Pitaevskii equations

A convergence analysis of time-splitting pseudo-spectral methods adapted for time-dependent Gross–Pitaevskii equations with additional rotation term is given. For the time integration high-order exponential operator splitting methods are studied, and the space discretization relies on the generalized-Laguerre–Fourier spectral method with respect to the $(x,y)$ -variables as well as the Hermite spectral method in the $z$ -direction. Essential ingredients in the stability and error analysis are a general functional analytic framework of abstract nonlinear evolution equations, fractional power spaces defined by the principal linear part, a Sobolev-type inequality in a curved rectangle, and results on the asymptotical distribution of the nodes and weights associated with Gauß–Laguerre quadrature. The obtained global error estimate ensures that the nonstiff convergence order of the time integrator and the spectral accuracy of the spatial discretization are retained, provided that the problem data satisfy suitable regularity requirements. A numerical example confirms the theoretical convergence estimate.     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Stochastic binary problems with simple penalties for capacity constraints violations

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly ${\mathcal{N}\mathcal{P}}$ -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.     

A-distributional summability in topological spaces

In the present paper we introduce a new concept of $A$ -distributional convergence in an arbitrary Hausdorff topological space which is equivalent to $A$ -statistical convergence for a degenerate distribution function. We investigate $A$ -distributional convergence as a summability method in an arbitrary Hausdorff topological space. We also study the summability of spliced sequences, in particular, for metric spaces and give the Bochner integral representation of $A$ -limits of the spliced sequences for Banach spaces.     

Using inexact gradients in a multilevel optimization algorithm

Many optimization algorithms require gradients of the model functions, but computing accurate gradients can be computationally expensive. We study the implications of using inexact gradients in the context of the multilevel optimization algorithm MG/Opt. MG/Opt recursively uses (typically cheaper) coarse models to obtain search directions for finer-level models. However, MG/Opt requires the gradient on the fine level to define the recursion. Our primary focus here is the impact of the gradient errors on the multilevel recursion. We analyze, partly through model problems, how MG/Opt is affected under various assumptions about the source of the error in the gradients, and demonstrate that in many cases the effect of the errors is benign. Computational experiments are included.