The application of sparse grid quadrature in solving stochastic optimisation problems

Abstract

Stochastic optimisation problems minimise expectations of random cost functions. Thus they require accurate quadrature methods in order to evaluate the objective. Promising methods based on sparse grids were shown to display high quadrature accuracy for smooth integrands. But they have negative quadrature weights which potentially destroy the convexity of the objective and thus may lead to totally wrong results. We prove here that, due to their high accuracy, sparse grids maintain the convexity of the objective for sufficiently fine grids. An application to optimal control demonstrates the superiority of sparse grids over Monte Carlo and product rule based approaches. References

• D. P. Bertsekas. Dynamic programming and optimal control. Vol. I. Athena Scientific, 2005. URL http://athenasc.com/dpbook.html.
• H.-J. Bungartz and M. Griebel. Sparse grids. Acta Numer., 13:147–269, 2004. doi:10.1017/S0962492904000182.
• M. Chen, S. Mehrotra, and D. Papp. Scenario generation for stochastic optimization problems via the sparse grid method. Comput. Optim. Appl., 62(3):669–692, 2015. doi:10.1007/s10589-015-9751-7.
• C. W. Clenshaw and A. R. Curtis. A method for numerical integration on an automatic computer. Numer. Math., 2:197–205, 1960. doi:10.1007/BF01386223.
• P. J. Davis and P. Rabinowitz. Methods of numerical integration. Computer Science and Applied Mathematics. Academic Press, 1984. doi:10.1016/C2013-0-10566-1.
• T. Gerstner and M. Griebel. Numerical integration using sparse grids. Numer. Algorithms, 18:209–232, 1998. doi:10.1023/A:1019129717644.
• M. Holtz. Sparse grid quadrature in high dimensions with applications in finance and insurance, volume 77 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, 2011. doi:10.1007/978-3-642-16004-2.
• B. Oksendal. Stochastic differential equations. Springer-Verlag, 1998. doi:10.1007/978-3-662-03620-4.
• T. N. L. Patterson. The optimum addition of points to quadrature formulae. Math. Comp., 22:847–856, 1968. doi:10.2307/2004583.
• S. W. Wallace and W. T. Ziemba. Applications of stochastic programming. MOS-SIAM Series on Optimization. SIAM, 2005. doi:10.1137/1.9780898718799.