Lower bounds and stochastic optimization algorithms for uniform designs with three or four levels

Fang, Kai-Tai; Maringer, Dietmar; Tang, Yu; Winker, Peter

doi:10.1090/S0025-5718-05-01806-5

Lower bounds and stochastic optimization algorithms for uniform designs with three or four levels
HTML articles powered by AMS MathViewer

by Kai-Tai Fang, Dietmar Maringer, Yu Tang and Peter Winker PDF

Math. Comp. 75 (2006), 859-878 Request permission

Abstract:

New lower bounds for three- and four-level designs under the centered $L_2$-discrepancy are provided. We describe necessary conditions for the existence of a uniform design meeting these lower bounds. We consider several modifications of two stochastic optimization algorithms for the problem of finding uniform or close to uniform designs under the centered $L_2$-discrepancy. Besides the threshold accepting algorithm, we introduce an algorithm named balance-pursuit heuristic. This algorithm uses some combinatorial properties of inner structures required for a uniform design. Using the best specifications of these algorithms we obtain many designs whose discrepancy is lower than those obtained in previous works, as well as many new low-discrepancy designs with fairly large scale. Moreover, some of these designs meet the lower bound, i.e., are uniform designs.

References

R. A. Bates, R. J. Buck, E. Riccomagno, and H. P. Wynn, Experimental design and observation for large systems, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 77–94, 95–111. With discussion and a reply by the authors. MR 1379235, DOI 10.1111/j.2517-6161.1996.tb02068.x
Kai-Tai Fang, Gen-Nian Ge, Min-Qian Liu, and Hong Qin, Construction of minimum generalized aberration designs, Metrika 57 (2003), no. 1, 37–50. MR 1963710, DOI 10.1007/s001840200197
Kai-Tai Fang, Xuan Lu, Yu Tang, and Jianxing Yin, Constructions of uniform designs by using resolvable packings and coverings, Discrete Math. 274 (2004), no. 1-3, 25–40. MR 2025074, DOI 10.1016/S0012-365X(03)00100-6
Kai-Tai Fang, Dennis K. J. Lin, Peter Winker, and Yong Zhang, Uniform design: theory and application, Technometrics 42 (2000), no. 3, 237–248. MR 1801031, DOI 10.2307/1271079
Kai-Tai Fang, Xuan Lu, and Peter Winker, Lower bounds for centered and wrap-around $L_2$-discrepancies and construction of uniform designs by threshold accepting, J. Complexity 19 (2003), no. 5, 692–711. MR 2003240, DOI 10.1016/S0885-064X(03)00067-0
Kai-Tai Fang, Chang-Xing Ma, and Peter Winker, Centered $L_2$-discrepancy of random sampling and Latin hypercube design, and construction of uniform designs, Math. Comp. 71 (2002), no. 237, 275–296. MR 1863000, DOI 10.1090/S0025-5718-00-01281-3
K.-T. Fang and Y. Wang, Number-theoretic methods in statistics, Monographs on Statistics and Applied Probability, vol. 51, Chapman & Hall, London, 1994. MR 1284470, DOI 10.1007/978-1-4899-3095-8
Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
Xuan Lu, Wenbiao Hu, and Yan Zheng, A systematical procedure in the construction of multi-level supersaturated design, J. Statist. Plann. Inference 115 (2003), no. 1, 287–310. MR 1984066, DOI 10.1016/S0378-3758(02)00116-7
Minqian Liu and Runchu Zhang, Construction of $E(s^2)$ optimal supersaturated designs using cyclic BIBDs, J. Statist. Plann. Inference 91 (2000), no. 1, 139–150. MR 1792369, DOI 10.1016/S0378-3758(00)00136-1
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Yuan Wang and Kai Tai Fang, A note on uniform distribution and experimental design, Kexue Tongbao (English Ed.) 26 (1981), no. 6, 485–489. MR 666355
Peter Winker, Optimization heuristics in econometrics, Wiley Series in Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 2001. Applications of threshold accepting. MR 1883767
P. Winker and K. T. Fang (1998), Optimal $U$-type design, in H. Niederreiter, P. Zinterhof, and P. Hellekalek (eds.), Monte Carlo and Quasi-Monte Carlo Methods 1996, Springer, 436–448.