Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms
Open Access
- 24 July 2023
- journal article
- research article
- Published by Springer Nature in Journal of Global Optimization
- Vol. 88 (1) , 1-26
Abstract
We consider global optimization problems, where the feasible region $${\mathcal {X}}$$ is a compact subset of $$\mathbb {R}^d$$ with $$d \ge 10$$ . For these problems, we demonstrate that 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, and that the usually recommended space exploration schemes are inefficient in the non-asymptotic regime. Moreover, we show that uniform sampling on entire $${\mathcal {X}}$$ is much less efficient than uniform sampling on a suitable subset of $${\mathcal {X}}$$ , and that the effect of replacement of random points by low-discrepancy sequences can be felt in small dimensions only.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Performance of global random search algorithms for large dimensionsJournal of Global Optimization, 2017
- On the worst-case optimal multi-objective global optimizationOptimization Letters, 2012
- Kernel techniques: From machine learning to meshless methodsActa Numerica, 2006
- Scattered Data Approximation2004
- Physical Experiments and Computer Experiments2003
- Centroidal Voronoi Tessellations: Applications and AlgorithmsSIAM Review, 1999
- A space quantization method for numerical integrationJournal of Computational and Applied Mathematics, 1998
- Random coverings in several dimensionsActa Mathematica, 1986
- Asymptotic quantization error of continuous signals and the quantization dimensionIEEE Transactions on Information Theory, 1982
- Minimization by Random Search TechniquesMathematics of Operations Research, 1981