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

Abstract

New lower bounds for three- and four-level designs under the centered <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L 2"> <mml:semantics> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">L_2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L 2"> <mml:semantics> <mml:msub> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">L_2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-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.