Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Kai-Tai Fang, Dietmar Maringer, Yu Tang and Peter Winker
Journal: Math. Comp. 75 (2006), 859-878
MSC (2000): Primary 68Q17, 68Q15, 62K99
DOI: https://doi.org/10.1090/S0025-5718-05-01806-5
Published electronically: December 27, 2005
MathSciNet review: 2196996
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. R. A. Bates, R. J. Buck, E. Riccomagno, and H. P. Wynn (1996), Experimental design and observation for large systems, Journal of Royal Statistical Society (B), 58, 77-94. MR 1379235 (96k:62213)
  • 2. K. T. Fang, G. N. Ge, M. Q. Liu, and H. Qin (2003), Construction on minimum generalized aberration designs, Metrika, 57, 37-50. MR 1963710 (2004b:62181)
  • 3. K. T. Fang, X. Lu, Y. Tang, and J. X. Yin (2004), Constructions of uniform designs by using resolvable packings and coverings, Discrete Mathematics, 274, 25-40. MR 2025074 (2004k:05057)
  • 4. K. T. Fang, D. K. J. Lin, P. Winker, and Y. Zhang (2000), Uniform Design: Theory and Application, Technometrics, 42, 237-248.MR 1801031
  • 5. K. T. Fang, X. Lu, and P. Winker (2003), Lower bounds for centered and wrap-around $ L_2$-discrepancies and construction of uniform design by threshold accepting, Journal of Complexity, 19, 692-711. MR 2003240 (2004g:62145)
  • 6. K. T. Fang, C. X. Ma, and P. Winker (2002), Centered $ L_2$-discrepancy of random sampling and Latin hypercube design, and construction of uniform designs, Mathematics of Computation, 71, 275-296.MR 1863000 (2002h:65024)
  • 7. K. T. Fang and Y. Wang (1994), Number-theoretic methods in statistics, Chapman and Hall, London. MR 1284470 (95g:65189)
  • 8. F. J. Hickernell (1998a), A generalized discrepancy and quadrature error bound, Mathematics of Computation, 67, 299-322. MR 1433265 (98c:65032)
  • 9. F. J. Hickernell (1998b), Lattice rules: how well do they measure up? in P. Hellekalek and G. Larcher (eds), Random and Quasi-Random Point Sets, Springer, 106-166. MR 1662841 (2000b:65007)
  • 10. X. Lu, W. B. Hu, and Y. Zheng (2003), A systematical procedure in the construction of multi-level supersaturated design, Journal of Statistical Planning and Inference, 115, 287-310. MR 1984066 (2004d:62272)
  • 11. M. Q. Liu and R. C. Zhang (2000), Construction of $ E(s^2)$ optimal supersaturated designs using cyclic BIBDs, Journal of Statistical Planning and Inference, 91, 139-150. MR 1792369 (2001h:62143)
  • 12. H. Niederreiter (1992), Random Number Generation and Quasi-Monte Carlo Methods, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia. MR 1172997 (93h:65008)
  • 13. Y. Wang and K. T. Fang (1981), A note on uniform distribution and experimental design, KeXue TongBao, 26, 485-489. MR 0666355 (83k:62109)
  • 14. P. Winker (2001), Optimization heuristics in econometrics: Applications of threshold accepting, Wiley, Chichester. MR 1883767 (2002k:62011)
  • 15. 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68Q17, 68Q15, 62K99

Retrieve articles in all journals with MSC (2000): 68Q17, 68Q15, 62K99


Additional Information

Kai-Tai Fang
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, People’s Republic of China
Email: ktfang@math.hkbu.edu.hk

Dietmar Maringer
Affiliation: Faculty of Economics, Law and Social Sciences, University of Erfurt, Germany
Email: dietmar.maringer@uni-erfurt.de

Yu Tang
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, People’s Republic of China
Address at time of publication: Department of Mathematics, Suzhou University, Suzhou, 215006, People’s Republic of China
Email: ytang@math.hkbu.edu.hk

Peter Winker
Affiliation: Faculty of Economics, Law and Social Sciences, University of Erfurt, Germany
Email: peter.winker@uni-erfurt.de

DOI: https://doi.org/10.1090/S0025-5718-05-01806-5
Keywords: Discrepancy, lower bound, uniform designs, stochastic optimization, threshold accepting
Received by editor(s): November 3, 2004
Published electronically: December 27, 2005
Additional Notes: The work was partially supported by the Grants GER/JRS/03-04/01, RGC/HKBU 200804, FRG/03-04/II-711, and DAAD D/03/314145.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society