Performance of global random search algorithms for large dimensions
Tóm tắt
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.
Tài liệu tham khảo
Auger, A., Hansen, N.: Theory of evolution strategies: a new perspective. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics: Foundations and Recent Developments, pp. 289–325. World Scientific Publishing, Singapore (2010)
Cooke, P.: Optimal linear estimation of bounds of random variables. Biometrika 67(1), 257–258 (1980)
De Haan, L.: Estimation of the minimum of a function using order statistics. J. Am. Stat. Assoc. 76(374), 467–469 (1981)
De Haan, L., Peng, L.: Comparison of tail index estimators. Stat. Neerl. 52(1), 60–70 (1998)
Dette, H., Pepelyshev, A., Zhigljavsky, A.: Optimal designs in regression with correlated errors. Ann. Stat. 44(1), 113–152 (2016)
Nevzorov, V.B.: Records: mathematical theory. American Mathematical Soc. (2001)
Niederreiter, H.: Random number generation and quasi-monte carlo methods, cbms-nsf reg. In: Conference of series applied mathematics, vol. 63 (1992)
Pintér, Jn: Convergence properties of stochastic optimization procedures. Optimization 15(3), 405–427 (1984)
Solis, F.J., Wets, R.J.B.: Minimization by random search techniques. Math. Oper. Res. 6(1), 19–30 (1981)
Zhigljavsky, A.: Monte-Carlo methods in global optimization, PhD thesis. Leningrad University (1981)
Zhigljavsky, A.: Mathematical Theory of Global Random Search. Leningrad University Press, Leningrad (1985). (in Russian)
Zhigljavsky, A.: Branch and probability bound methods for global optimization. Informatica 1(1), 125–140 (1990)
Zhigljavsky, A.: Theory of Global Random Search. Kluwer Academic Publishers, Boston (1991)
Zhigljavsky, A., Hamilton, E.: Stopping rules in k-adaptive global random search algorithms. J. Glob. Optim. 48(1), 87–97 (2010)
Zhigljavsky, A., Žilinskas, A.: Methods of Seeking a Global Extremum. Nauka, Moscow (1991)
Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, New York (2008)
Zhigljavsky, A.A.: Semiparametric statistical inference in global random search. Acta Applicandae Mathematica 33(1), 69–88 (1993)
Žilinskas, A.: A statistical model-based algorithm for black-box multi-objective optimisation. Int. J. Syst. Sci. 45(1), 82–92 (2014)
Žilinskas, A., Zhigljavsky, A.: Branch and probability bound methods in multi-objective optimization. Optim. Lett. 10(2), 341–353 (2016)