(254g) Novel Optimization-Based Adaptive Sparse-Grid Methods for Numerical Integration

The Smolyak algorithm (also known as Sparse-Grid, Hyperbolic Cross-Points or Boolean method) was derived in 1963 by Russian mathematician Smolyak, and was based on the fact that spaces of n-dimensional continuous linear functionals contain tensor products of spaces of continuous linear functionals on the one-dimensional space [1]. This development was followed by a plethora of advances in theory, methods and applications, due to the realization that high-dimensional tensor product problems can be solved efficiently using accurate n-dimensional approximations which can be generated from univariate approximations [2]. Sparse-grid methods have been used for approximation, integration and optimization in mathematics, physics, economics and engineering design [3-5]. Two of their main advantages are (a) sparse-grid tensor products do not grow exponentially with dimension n (curse-of-dimensionality), and (b) convergence rates and error-bound analysis are available as a function of smoothness of the function within a bounded region.

In this work, we aim to show the power of this extremely mathematically-rich theory, and extend the capabilities of existing methods by combining existing theory with theory from deterministic optimization. Specifically, we have developed a computational tool for multidimensional integration of functions, using the Smolyak algorithm with a variety of univariate quadrature rules, such as Clenshaw-Curtis, Gauss-Patterson and Fejer rules. These rules are based on roots or extrema of orthogonal polynomials and lead to non-equidistant sparse tensor grids, which perform exceptionally well with fewer number of sample points, when compared to equidistant full-tensor grid points. We have incorporated a newly derived formula for the efficient calculation of the weights for the calculation of multidimensional integrals. This derivation circumvents a main hurdle in the Smolyak algorithm, namely the problem of redundant weights which significantly increases the computational cost of the method [3]. This development allows us to push the limits of high dimensional integration, which we will show through benchmark cubature problems. Furthermore, we have incorporated an approach for the further reduction of the total number of points required for accurate multidimensional integral calculation, using ideas from adaptive-sparse grids [6-7] and optimization. Overall, this talk aims to introduce significant theoretical and methodological advances, which have a wide range of applications in the field of chemical engineering.

1. Smolyak, S. A. (1963). Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions. Soviet Math. Dokl., 4, 240-243

2. Novak, E., Ritter, K. (1996). High dimensional integration of smooth functions over cubes, Numer. Math. 75, 79-97

3. Judd, K.L., Maliar, L., Maliar, S., Valero, R. (2014). Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain. J of Economic Dynamics & Control, 44, 92-123

4. Bohn, B., Garcke, J., Griebel, M. (2016). A Sparse-Grid Based Method for Generative Dimensionality Reduction of High-Dimensional Data. J of Comp Physics, 309, 1-17

5. Malin, B., Krueger, D., Kubler, F. (2011). Solving the multi-country real business cycle model using a Smolyak-collocation method. J of Economic Dynamics & Control, 35, 229-239

6. Gerstner, T., Griebel, M. (2003) Dimension-Adaptive Tensor-Product Quadrature. Computing, 71, 65-87

7. Bungartz, H.J., Dirnstorfer, S. (2003). Multivariate Quadrature on Adaptive Sparse Grids. Computing, 71, 89-114