TY - JOUR

T1 - Performance of global random search algorithms for large dimensions

AU - Pepelyshev, Andrey

AU - Zhigljavsky, Anatoly

AU - Žilinskas, Antanas

PY - 2018/5/1

Y1 - 2018/5/1

N2 - We investigate the rate of convergence of general global random search (GRS) algorithms. We show that if the dimension of the feasible domain is large then it is impossible to give any guarantee that the global minimizer is found by a general GRS algorithm with reasonable accuracy. We then study precision of statistical estimates of the global minimum in the case of large dimensions. We show that these estimates also suffer the curse of dimensionality. Finally, we demonstrate that the use of quasi-random points in place of the random ones does not give any visible advantage in large dimensions.

AB - We investigate the rate of convergence of general global random search (GRS) algorithms. We show that if the dimension of the feasible domain is large then it is impossible to give any guarantee that the global minimizer is found by a general GRS algorithm with reasonable accuracy. We then study precision of statistical estimates of the global minimum in the case of large dimensions. We show that these estimates also suffer the curse of dimensionality. Finally, we demonstrate that the use of quasi-random points in place of the random ones does not give any visible advantage in large dimensions.

KW - Extreme value statistics

KW - Global optimization

KW - Random search

KW - Statistical models

UR - http://www.scopus.com/inward/record.url?scp=85020083322&partnerID=8YFLogxK

U2 - 10.1007/s10898-017-0535-8

DO - 10.1007/s10898-017-0535-8

M3 - Article

AN - SCOPUS:85020083322

VL - 71

SP - 57

EP - 71

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 1

ER -