Optimal point sets for quasi-Monte Carlo integration of bivariate periodic functions with bounded mixed derivatives
This provides a theoretical justification for the optimality of Fibonacci lattices in QMC integration, addressing a fundamental question for practitioners in numerical analysis.
The authors prove that the Fibonacci lattice is the unique global minimizer of the worst-case quasi-Monte Carlo integration error for bivariate periodic functions with bounded mixed derivatives for small N, and show that for N=1,2,3,5,7,8,12,13 the optimal point sets are integration lattices.
We investigate quasi-Monte Carlo (QMC) integration of bivariate periodic functions with dominating mixed smoothness of order one. While there exist several QMC constructions which asymptotically yield the optimal rate of convergence of $\mathcal{O}(N^{-1}\log(N)^{\frac{1}{2}})$, it is yet unknown which point set is optimal in the sense that it is a global minimizer of the worst case integration error. We will present a computer-assisted proof by exhaustion that the Fibonacci lattice is the unique minimizer of the QMC worst case error in periodic $H^1_\text{mix}$ for small $N$. Moreover, we investigate the situation for pointsets whose cardinality $N$ is not a Fibonacci number. It turns out that for $N=1,2,3,5,7,8,12,13$ the optimal point sets are integration lattices.