Minimax and maximin space-filling designs: some properties and methods for construction

Pronzato, Luc

Journal de la société française de statistique, Special Issue : Computer Experiments, Uncertainty and Sensitivity Analysis, Tome 158 (2017) no. 1, pp. 7-36.

Cet article présente quelques propriétés de plans d’expériences minimax et maximin optimaux dans un compact de ${ℝ}^d$, ainsi que leur relations avec d’autres plans “à remplissage d’espace”. Plusieurs méthodes sont indiquées pour l’évaluation du critère de distance minimax (ou dispersion) pour un plan donné à $n$ points. Diverses méthodes d’optimisation sont proposées et leurs limitations sont indiquées, en particulier en terme de dimension $d$. La grande majorité des résultats présentés ne sont pas nouveaux, mais nous espérons que le lecteur trouvera utile de les voir réunis dans un seul document accompagné d’une bibliographie conséquente.

A few properties of minimax and maximin optimal designs in a compact subset of ${ℝ}^d$ are presented, and connections with other space-filling constructions are indicated. Several methods are given for the evaluation of the minimax-distance (or dispersion) criterion for a given $n$-point design. Various optimisation methods are proposed and their limitations, in particular in terms of dimension $d$, are indicated. A large majority of the results presented are not new, but their collection in a single document containing a respectable bibliography will hopefully be useful to the reader.

[Aaron et al., 2014] Aaron, C., Cholaquidis, A., and Fraiman, R. (2014). On the maximal multivariate spacing extension and convexity tests. arXiv preprint arXiv:1411.2482.

[Atkinson et al., 2007] Atkinson, A., Donev, A., and Tobias, R. (2007). Optimum Experimental Designs, with SAS. Oxford University Press. | MR

[Audze and Eglais, 1977] Audze, P. and Eglais, V. (1977). New approach for planning out of experiments. Problems of Dynamics and Strengths, 35:104–107.

[Auffray et al., 2012] Auffray, Y., Barbillon, P., and Marin, J.-M. (2012). Maximin design on non hypercube domains and kernel interpolation. Statistics and Computing, 22(3):703–712. | MR | Zbl

[Basseville, 2013] Basseville, M. (2013). Divergence measures for statistical data processing — An annotated bibliography. Signal Processing, 93(4):621–633.

[Bates et al., 1996] Bates, R., Buck, R., Riccomagno, E., and Wynn, H. (1996). Experimental design and observation for large systems. Journal of the Royal Statistical Society. Series B (Methodological), pages 77–94. | MR | Zbl

[Beardwood et al., 1959] Beardwood, J., Halton, J., and Hammersley, J. (1959). The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society, 55(4):299–327. | MR | Zbl

[Berlinet and Thomas-Agnan, 2004] Berlinet, A. and Thomas-Agnan, C. (2004). Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer, Boston. | MR | Zbl

[Bertsimas and Tsitsiklis, 1993] Bertsimas, D. and Tsitsiklis, J. (1993). Simulated annealing. Statistical Science, 8(1):10–15.

[Biedermann and Dette, 2001] Biedermann, S. and Dette, H. (2001). Minimax optimal designs for nonparametric regression — a further optimality property of the uniform distribution. In A.C. Atkinson, P. H. and Müller, W., editors, mODa’6 – Advances in Model–Oriented Design and Analysis, Proceedings of the 76th Int. Workshop, Puchberg/Schneeberg (Austria), pages 13–20, Heidelberg. Physica Verlag. | MR

[Blum et al., 2016] Blum, A., Hopcroft, J., and Kannan, R. (2016). Foundations of Data Science. http://www.cs.cornell.edu/jeh/bookJan25_2016.pdf.

[Boissonnat and Yvinec, 1998] Boissonnat, J.-D. and Yvinec, M. (1998). Algorithmic Geometry. Cambridge University Press. | MR

[Bonnans et al., 2006] Bonnans, J., Gilbert, J., Lemaréchal, C., and Sagastizábal, C. (2006). Numerical Optimization. Theoretical and Practical Aspects. Springer, Heidelberg. [2nd ed.]. | MR | Zbl

[Botkin and Turova-Botkina, 1994] Botkin, N. and Turova-Botkina, V. (1994). An algorithm for finding the Chebyshev center of a convex polyhedron. Applied Mathematics and Optimization, 29:211–222. | MR | Zbl

[Cignoni et al., 1998] Cignoni, P., Montani, C., and Scopigno, R. (1998). DeWall: A fast divide and conquer Delaunay triangulation algorithm in $E^d$. Computer-Aided Design, 30(5):333–341. | Zbl

[Conway and Sloane, 1999] Conway, J. and Sloane, N. (1999). Sphere Packings, Lattices and Groups. Springer, New York. [3rd ed.]. | MR

[Cortés and Bullo, 2005] Cortés, J. and Bullo, F. (2005). Coordination and geometric optimization via distributed dynamical systems. SIAM Journal on Control and Optimization, 44(5):1543–1574. | MR | Zbl

[Cortés and Bullo, 2009] Cortés, J. and Bullo, F. (2009). Nonsmooth coordination and geometric optimization via distributed dynamical systems. SIAM Review, 51(1):163–189. | MR | Zbl

[Croft et al., 1991] Croft, H., Falconer, K., and Guy, R. (1991). Unsolved Problems in Geometry. Springer, New York. | MR

[Dem’yanov and Malozemov, 1974] Dem’yanov, V. and Malozemov, V. (1974). Introduction to Minimax. Dover, New York. | MR

[Du et al., 1999] Du, Q., Faber, V., and Gunzburger, M. (1999). Centroidal Voronoi tessellations: applications and algorithms. SIAM Review, 41(4):637–676. | MR | Zbl

[Durrande et al., 2012] Durrande, N., Ginsbourger, D., and Roustant, O. (2012). Additive covariance kernels for high-dimensional Gaussian process modeling. Annales de la Faculté de Sciences de Toulouse, 21(3):481–499. | Numdam | MR | Zbl

[Fang et al., 2006] Fang, K.-T., Li, R., and Sudjianto, A. (2006). Design and Modeling for Computer Experiments. Chapman & Hall/CRC, Boca Raton. | MR | Zbl

[Fang et al., 2003] Fang, K.-T., Lu, X., and Winker, P. (2003). Lower bounds for centered and wrap-around $L_2$-discrepancies and construction of uniform designs by threshold accepting. Journal of Complexity, 19(5):692–711. | MR | Zbl

[Fang and Ma, 2001] Fang, K.-T. and Ma, C.-X. (2001). Wrap-around $L_2$-discrepancy of random sampling, Latin hypercube and uniform designs. Journal of Complexity, 17(4):608–624. | MR | Zbl

[Fang et al., 2005] Fang, K.-T., Tang, Y., and Yin, J. (2005). Lower bounds for wrap-around $L_2$-discrepancy and constructions of symmetrical uniform designs. Journal of Complexity, 21(5):757–771. | MR | Zbl

[Fedorov, 1972] Fedorov, V. (1972). Theory of Optimal Experiments. Academic Press, New York. | MR

[Fedorov, 1996] Fedorov, V. (1996). Design of spatial experiments: model fitting and prediction. In Gosh, S. and Rao, C., editors, Handbook of Statistics, vol. 13, chapter 16, pages 515–553. Elsevier, Amsterdam. | MR | Zbl

[Fedorov and Leonov, 2014] Fedorov, V. and Leonov, S. (2014). Optimal Design for Nonlinear Response Models. CRC Press, Boca Raton. | MR

[Flury, 1993] Flury, B. (1993). Estimation of principal points. Applied Statistics, 42(1):139–151. | MR | Zbl

[Franco et al., 2009] Franco, J., Vasseur, O., Corre, B., and Sergent, M. (2009). Minimum Spanning Tree: a new approach to assess the quality of the design of computer experiments. Chemometrics and Intelligent Laboratory Systems, 97:164–169.

[Gauthier and Pronzato, 2014] Gauthier, B. and Pronzato, L. (2014). Spectral approximation of the IMSE criterion for optimal designs in kernel-based interpolation models. SIAM/ASA J. Uncertainty Quantification, 2:805–825. DOI 10.1137/130928534. | MR

[Gauthier and Pronzato, 2016] Gauthier, B. and Pronzato, L. (2016). Convex relaxation for IMSE optimal design in random field models. Computational Statistics and Data Analysis (to appear). hal-01246483. | MR

[Ginsbourger et al., 2014] Ginsbourger, D., Roustant, O., Schuhmacher, D., Durrande, N., and Lenz, N. (2014). On ANOVA decompositions of kernels and Gaussian random field paths. preprint arXiv:1409.6008. | MR

[Gonzalez, 1985] Gonzalez, T. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306. | MR | Zbl

[Graham and Lubachevsky, 1996] Graham, R. and Lubachevsky, B. (1996). Repeated patterns of dense packings of equal disks in a square. The Electronic Journal of Combinatorics, 3(1):R16. | MR

[Graham et al., 1998] Graham, R., Lubachevsky, B., Nurmela, K., and Östergård, P. (1998). Dense packings of congruent circles in a circle. Discrete Mathematics, 181(1):139–154. | MR | Zbl

[Guyader et al., 2011] Guyader, A., Hengartner, N., and Matzner-Løber, E. (2011). Simulation and estimation of extreme quantiles and extreme probabilities. Applied Mathematics & Optimization, 64(2):171–196. | MR | Zbl

[Hardin and Saff, 2004] Hardin, D. and Saff, E. (2004). Discretizing manifolds via minimum energy points. Notices of the AMS, 51(10):1186–1194. | MR | Zbl

[Harman and Pronzato, 2007] Harman, R. and Pronzato, L. (2007). Improvements on removing non-optimal support points in $D$-optimum design algorithms. Statistics & Probability Letters, 77:90–94. | MR | Zbl

[Hickernell, 1998a] Hickernell, F. (1998a). A generalized discrepancy and quadrature error bound. Mathematics of Computation, 67(221):299–322. | MR | Zbl

[Hickernell, 1998b] Hickernell, F. (1998b). Lattice rules: how well do they measure up? In Helekalek, P. and Larcher, G., editors, Random and Quasi-Random Point Sets, volume 138 of Lecture Notes in Statist., pages 109–166. Springer, New York. | MR | Zbl

[Janson, 1986] Janson, S. (1986). Random coverings in several dimensions. Acta Mathematica, 156(1):83–118. | MR | Zbl

[Janson, 1987] Janson, S. (1987). Maximal spacings in several dimensions. The Annals of Probability, 15(1):274–280. | MR | Zbl

[Johnson et al., 1990] Johnson, M., Moore, L., and Ylvisaker, D. (1990). Minimax and maximin distance designs. Journal of Statistical Planning and Inference, 26:131–148. | MR

[Joseph et al., 2015] Joseph, V., Gul, E., and Ba, S. (2015). Maximum projection designs for computer experiments. Biometrika, 102(2):371–380. | MR

[Jourdan and Franco, 2009a] Jourdan, A. and Franco, J. (2009a). A new criterion based on Kullback-Leibler information for space filling designs. preprint arXiv:0904.2456, hal-00375820.

[Jourdan and Franco, 2009b] Jourdan, A. and Franco, J. (2009b). Plans d’expériences numériques d’information de Kullback-Leibler minimale. Journal de la Société Française de Statistique, 150(2):52–64. | Numdam | MR

[Jourdan and Franco, 2010] Jourdan, A. and Franco, J. (2010). Optimal Latin hypercube designs for the Kullback–Leibler criterion. AStA Advances in Statistical Analysis, 94(4):341–351. | MR

[Kennard and Stone, 1969] Kennard, R. and Stone, L. (1969). Computer aided design of experiments. Technometrics, 11(1):137–148. | Zbl

[Kesten, 1958] Kesten, H. (1958). Accelerated stochastic approximation. The Annals of Mathematical Statistics, 29(1):41–59. | MR | Zbl

[Klee, 1980] Klee, V. (1980). On the complexity of $d$-dimensional Voronoi diagrams. Archiv der Mathematik, 34(1):75–80. | MR | Zbl

[Korobov, 1960] Korobov, N. (1960). Properties and calculation of optimal coefficients. Doklady Akademii Nauk SSSR, 132(5):1009–1012. | MR | Zbl

[Kozachenko and Leonenko, 1987] Kozachenko, L. and Leonenko, N. (1987). On statistical estimation of entropy of random vector. Problems Infor. Transmiss., 23(2):95–101. (translated from Problemy Peredachi Informatsii, in Russian, vol. 23, No. 2, pp. 9-16, 1987). | MR | Zbl

[Lagarias, 2011] Lagarias, J., editor (2011). The Kepler Conjecture: The Hales-Ferguson Proof. Springer, New York. | MR

[Landkof, 1972] Landkof, N. (1972). Foundations of Modern Potential Theory. Springer, Berlin. | MR

[Lekivetz and Jones, 2015] Lekivetz, R. and Jones, B. (2015). Fast flexible space-filling designs for nonrectangular regions. Quality and Reliability Engineering International, 31(5):829–837.

[Leonenko et al., 2008] Leonenko, N., Pronzato, L., and Savani, V. (2008). A class of Rényi information estimators for multidimensional densities. Annals of Statistics, 36(5):2153–2182 (Correction in AS, 38(6):3837–3838, 2010). | MR | Zbl

[Lloyd, 1982] Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137. | MR | Zbl

[Lubachevsky, 1991] Lubachevsky, B. (1991). How to simulate billiards and similar systems. Journal of Computational Physics, 94(2):255–283. | MR | Zbl

[Lubachevsky and Stillinger, 1990] Lubachevsky, B. and Stillinger, F. (1990). Geometric properties of random disk packings. Journal of Statistical Physics, 60(5-6):561–583. | MR | Zbl

[MacQueen, 1967] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In LeCam, L. and Neyman, J., editors, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281–297. | MR | Zbl

[Maranas et al., 1995] Maranas, C., Floudas, C., and Pardalos, P. (1995). New results in the packing of equal circles in a square. Discrete Mathematics, 142(1):287–293. | MR | Zbl

[Marengo and Todeschini, 1992] Marengo, E. and Todeschini, R. (1992). A new algorithm for optimal, distance-based, experimental design. Chemometrics and Intelligent Laboratory Systems, 16:37–44.

[Markót and Csendes, 2005] Markót, M. and Csendes, T. (2005). A new verified optimization technique for the “packing circles in a unit square” problems. SIAM Journal on Optimization, 16(1):193–219. | MR | Zbl

[Mitchell, 1990] Mitchell, R. (1990). Error estimates arising from certain pseudorandom sequences in a quasirandom search method. Mathematics of Computation, 55(191):289–297. | MR | Zbl

[Müller, 2001] Müller, W. (2001). Coffee-house designs. In Atkinson, A., Bogacka, B., and Zhigljavsky, A., editors, Optimum Design 2000, chapter 21, pages 241–248. Kluwer, Dordrecht. | MR

[Müller, 2007] Müller, W. (2007). Collecting Spatial Data. Springer, Berlin. [3rd ed.]. | MR

[Niederreiter, 1992] Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia. | MR

[Nurmela and Östergård, 1997] Nurmela, K. and Östergård, P. (1997). Packing up to 50 equal circles in a square. Discrete & Computational Geometry, 18(1):111–120. | MR | Zbl

[Nurmela and Östergård, 1999] Nurmela, K. and Östergård, P. (1999). More optimal packings of equal circles in a square. Discrete & Computational Geometry, 22(3):439–457. | MR | Zbl

[Nuyens, 2007] Nuyens, D. (2007). Fast construction of good lattice rules. Ph.D. Thesis, Katholieke Univ. Leuven.

[Okabe et al., 1992] Okabe, A., Books, B., Sugihama, K., and Chiu, S. (1992). Spatial Tessellations. Concepts and Applications of Voronoi Diagrams. Wiley, New York. | MR

[Oler, 1961] Oler, N. (1961). A finite packing problem. Canadian Mathematical Bulletin, 4:153–155. | MR | Zbl

[Penrose and Yukich, 2003] Penrose, M. and Yukich, J. (2003). Weak laws of large numbers in geometric probability. The Annals of Applied Probability, 13(1):277–303. | MR | Zbl

[Penrose and Yukich, 2011] Penrose, M. and Yukich, J. (2011). Laws of large numbers and nearest neighbor distances. In Wells, M. and Sengupta, A., editors, Advances in Directional and Linear Statistics. A Festschrift for Sreenivasa Rao Jammalamadaka, pages 189–199. Springer. | MR

[Persson and Strang, 2004] Persson, P.-O. and Strang, G. (2004). A simple mesh generator in MATLAB. SIAM review, 46(2):329–345. | MR | Zbl

[Pilz, 1983] Pilz, J. (1983). Bayesian Estimation and Experimental Design in Linear Regression Models, volume 55. Teubner-Texte zur Mathematik, Leipzig. (also Wiley, New York, 1991). | MR | Zbl

[Pronzato and Müller, 2012] Pronzato, L. and Müller, W. (2012). Design of computer experiments: space filling and beyond. Statistics and Computing, 22:681–701. | MR | Zbl

[Pronzato and Pázman, 2013] Pronzato, L. and Pázman, A. (2013). Design of Experiments in Nonlinear Models. Asymptotic Normality, Optimality Criteria and Small-Sample Properties. Springer, LNS 212, New York. | MR | Zbl

[Pronzato et al., 2016a] Pronzato, L., Wynn, H., and Zhigljavsky, A. (2016a). Extended generalised variances, with applications. Bernoulli (to appear). arXiv preprint arXiv:1411.6428, hal-01308092. | MR

[Pronzato et al., 2016b] Pronzato, L., Wynn, H., and Zhigljavsky, A. (2016b). Extremal measures maximizing functionals based on simplicial volumes. Statistical Papers (to appear). hal-01308116. | MR

[Pukelsheim, 1993] Pukelsheim, F. (1993). Optimal Experimental Design. Wiley, New York. | Zbl

[Rasmussen and Williams, 2006] Rasmussen, C. and Williams, C. (2006). Gaussian Processes for Machine Learning. MIT Press, Cambridge (MA), USA. | MR | Zbl

[Redmond and Yukich, 1994] Redmond, C. and Yukich, J. (1994). Limit theorems and rates of convergence for euclidean functionals. The Annals of Applied Probability, 4(4):1057–1073. | MR | Zbl

[Redmond and Yukich, 1996] Redmond, C. and Yukich, J. (1996). Asymptotics for Euclidian functionals with power-weighted edges. Stochastic Processes and their Applications, 61:289–304. | MR | Zbl

[Riccomagno et al., 1997] Riccomagno, E., Schwabe, R., and Wynn, H. (1997). Lattice-based D-optimum design for Fourier regression. Annals of Statistics, 25(6):2313–2327. | MR | Zbl

[Roberts and Rosenthal, 2006] Roberts, G. and Rosenthal, J. (2006). Harris recurrence of Metropolis-within-Gibbs and trans-dimensional Markov chains. The Annals of Applied Probability, 6(4):2123–2139. | MR | Zbl

[Royle and Nychka, 1998] Royle, J. and Nychka, D. (1998). An algorithm for the construction of spatial coverage designs with implementation in SPLUS. Computers and Geosciences, 24(5):479–488.

[Sacks et al., 1989] Sacks, J., Welch, W., Mitchell, T., and Wynn, H. (1989). Design and analysis of computer experiments. Statistical Science, 4(4):409–435. | MR | Zbl

[Saff, 2010] Saff, E. (2010). Logarithmic potential theory with applications to approximation theory. Surveys in Approximation Theory, 5(14):165–200. | MR | Zbl

[Santner et al., 2003] Santner, T., Williams, B., and Notz, W. (2003). The Design and Analysis of Computer Experiments. Springer, Heidelberg. | MR

[Schaback, 1995] Schaback, R. (1995). Error estimates and condition numbers for radial basis function interpolation. Advances in Computational Mathematics, 3(3):251–264. | MR | Zbl

[Shewry and Wynn, 1987] Shewry, M. and Wynn, H. (1987). Maximum entropy sampling. Applied Statistics, 14:165–170.

[Silvey, 1980] Silvey, S. (1980). Optimal Design. Chapman & Hall, London. | MR

[Sinai and Chernov, 1987] Sinai, Y. and Chernov, N. (1987). Ergodic properties of certain systems of two-dimensional discs and three-dimensional balls. Russian Mathematical Surveys, 42(3):181–207. | MR | Zbl

[Sloan and Reztsov, 2002] Sloan, I. and Reztsov, A. (2002). Component-by-component construction of good lattice rules. Mathematics of Computation, 71(237):263–273. | MR | Zbl

[Sloan and Walsh, 1990] Sloan, I. and Walsh, L. (1990). A computer search of rank-2 lattice rules for multidimensional quadrature. Mathematics of Computation, 54(189):281–302. | MR | Zbl

[Spöck and Pilz, 2010] Spöck, G. and Pilz, J. (2010). Spatial sampling design and covariance-robust minimax prediction based on convex design ideas. Stochastic Environmental Research and Risk Assessment, 24(3):463–482.

[Steele, 1981] Steele, J. (1981). Subadditive Euclidean functionals and nonlinear growth in geometric probability. The Annals of Probability, pages 365–376. | MR | Zbl

[Stein, 1999] Stein, M. (1999). Interpolation of Spatial Data. Some Theory for Kriging. Springer, Heidelberg. | MR | Zbl

[Sukharev, 1992] Sukharev, A. (1992). Minimax Models in the Theory of Numerical Methods. Springer (originally, Kluwer Academic Publishers), Dordrecht. | MR

[Tierney, 1998] Tierney, L. (1998). A note on Metropolis-Hastings kernels for general state spaces. Annals of Applied Probability, 8(1):1–9. | MR | Zbl

[Vallentin, 2003] Vallentin, F. (2003). Sphere coverings, lattices and tilings. Ph.D. Thesis, Technischen Universität München, Germany.

[Vazquez and Bect, 2011] Vazquez, E. and Bect, J. (2011). Sequential search based on kriging: convergence analysis of some algorithms. Proc. 58th World Statistics Congress of the ISI, August 21-26, Dublin, Ireland, arXiv preprint arXiv:1111.3866v1.

[Viazovska, 2016] Viazovska, M. (2016). The sphere packing problem in dimension 8. arXiv preprint arXiv:1603.04246. | MR

[Wade, 2007] Wade, A. (2007). Explicit laws of large numbers for random nearest-neighbour-type graphs. Advances in Applied Probability, 39(2):326–342. | MR | Zbl

[Wahl et al., 2014] Wahl, F., Mercadier, C., and Helbert, C. (2014). Measuring the quality of maximin space-filling designs. hal-00955294.

[Walter and Piet-Lahanier, 1989] Walter, E. and Piet-Lahanier, H. (1989). Exact recursive polyhedral description of the feasible parameter set for bounded error models. IEEE Transactions on Automatic Control, 34:911–915. | MR | Zbl

[Ward Jr., 1963] Ward Jr., J. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236–244. | MR

[Xu et al., 2003] Xu, S., Freund, R., and Sun, J. (2003). Solution methodologies for the smallest enclosing circle problem. Computational Optimization and Applications, 25(1-3):283–292. | MR | Zbl

[Yildirim, 2008] Yildirim, E. (2008). Two algorithms for the minimum enclosing ball problem. SIAM Journal on Optimization, 19(3):1368–1391. | MR | Zbl

[Yukich, 1998] Yukich, J. (1998). Probability Theory of Classical Euclidean Optimization Problems. Springer, Berlin. | MR | Zbl

[Zhigljavsky et al., 2010] Zhigljavsky, A., Dette, H., and Pepelyshev, A. (2010). A new approach to optimal design for linear models with correlated observations. Journal of the American Statistical Association, 105(491):1093–1103. | MR

[Zhigljavsky and Hamilton, 2010] Zhigljavsky, A. and Hamilton, E. (2010). Stopping rules in $k$-adaptive global random search algorithms. Journal of Global Optimization, 48(1):87–97. | MR | Zbl

[Zhigljavsky and Žilinskas, 2007] Zhigljavsky, A. and Žilinskas, A. (2007). Stochastic Global Optimization. Springer, New York. | MR