Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms

We consider global optimization problems, where the feasible region X is a compact subset of ℝd with d ≥ 10. For these problems, we demonstrate the following. First: the actual convergence of global random search algorithms is much slower than that given by the classical estimates, based on the asymptotic properties of random points. Second: the usually recommended space exploration schemes are inefficient in the non-asymptotic regime. Specifically, (a) uniform sampling on entire~X is much less efficient than uniform sampling on a suitable subset of X, and (b) the effect of replacement of random points by low-discrepancy sequences is negligible.