The Sparse Grid Combination Technique for Functionals with Applications

Abstract

The sparse grid method is a special discretisation technique used to solve high dimensional problems. There are a wide range of applications of the sparse grid method in calculating high dimensional integrals and the solution of high dimensional PDEs. The sparse grid combination technique is a kind of method used to approximate the numerical result of the sparse grid method. The general idea of the sparse grid combination technique is to compute a linear combination of approximations of the solution of the problem. The approximations are computed on some anisotropic regular grids. The combination technique is based on the inclusion-exclusion principle. Compared with the sparse grid method, there are two advantages of the combination technique. First, only nodal basis functions are required in combination technique rather than the hierarchical basis functions in sparse grid method. Second, the combination technique is easier for parallelisation. Generalised combination techniques, e.g. the truncated combination technique, the dimension-adaptive combination technique etc, are developed to further reduce the cost when solving a high dimensional problem.

For many real world problems, people are interested in some functionals related to the solution of the problem rather than the solution itself. These functionals which capture the important features of the problem are usually key for people to further understand it. When a high dimensional problem is considered, the computational cost of the functionals can be large since the numerical solution of a high dimensional partial differential equation is usually expensive to compute. We apply the generalised combination techniques to reducing the cost of computation of important functionals. Our method is based on the error models of the functionals. We build the error models for some special types of functionals when numerical schemes used to compute the PDEs and the functionals are known. We show the connection between the decay of the surpluses and the error models. By using the connection, we can also apply generalised combination techniques to functionals when we only know their computed surpluses. Numerical experiments are provided to illustrate error models for the functionals and the performance of our generalised combination techniques.

Stochastic optimisation problems minimise expectations of random cost functions. Thus they require accurate quadrature methods in order to evaluate the objective, gradient and Hessian which appear in the computation. Two categories of methods are studied here. One is the discretise then optimise method, the other is the optimise then discretise method. For the methods in the first category, the application of the sparse grid methods leads to high quadrature accuracy in approximating the objective. However, the sparse grid surrogates have negative quadrature weights which potentially destroy the convexity of the objective and thus may lead to totally wrong results. We prove that the sparse grid surrogates maintain the convexity of the objective for sufficiently fine grids. For the methods in the second category, it is more flexible for us to choose the numerical schemes which used to approximate the objective, gradient and Hessian. Therefore, the application of the dimension adaptive method is possible and reasonable for optimise then discretise approaches. It further reduces the computational costs and has even better performance compared with the classical sparse grid method for many stochastic optimisation problems. Applications are provided to demonstrate the superiority of our approaches over the classical Monte Carlo and product rule based approaches. Show more