On Using the Decision Trees to Identify the Local Extrema in Parallel Global Optimization Algorithm

Konstantin A. Barkalov, Ilya G. Lebedev, Dmitry I. Silenko

Аннотация


In the present work, the solving of the multidimensional global optimization problems using decision tree to reveal the attractor regions of the local minima is considered. The objective function of the problem is defined as a “black box”, may be non-differentiable, multi-extremal and computational costly. We assume that the function satisfies the Lipschitz condition with a priory unknown constant. Global search algorithm is applied for the search of global minimum in the problems of such type. It is well known that the solution complexity essentially depends on the presence of multiple local extrema. Within the framework of the global search algorithm, we propose a method for selecting the vicinity of local extrema of the objective function based on analysis of accumulated search information. Conducting such an analysis using machine learning techniques allows making a decision to run a local method, which can speed up the convergence of the algorithm. This suggestion was confirmed by the results of numerical experiments demonstrating the speedup when solving a series of test problems.

Ключевые слова


global optimization; multiextremal functions; parallel computing; machine learning; decision tree

Полный текст:

PDF (English)

Литература


Ferreiro A., Garcia J., Lopez-Salas J., Vazquez C. An efficient implementation of parallel simulated annealing algorithm in GPUs. J. Glob. Optim. 2013. Vol. 57, no. 3. P. 863–890. DOI: 10.1007/s10898-012-9979-z.

Garcia-Martinez J., Garzon E., Ortigosa P. A GPU implementation of a hybrid evolutionary algorithm: GPuEGO. J. Supercomput. 2014. Vol. 70, no. 2. P. 684–695. DOI: 10.1007/s11227-014-1136-7.

Langdon W. Graphics processing units and genetic programming: an overview. Soft Computing. 2011. Vol. 15, no. 8. P. 1657–1669. DOI: 10.1007/s00500-011-0695-2.

Evtushenko Y., Malkova V., Stanevichyus A.A. Parallel global optimization of functions of several variables. Comput. Math. Math. Phys. 2009. Vol. 49, no. 2. P. 246–260. DOI: 10.1134/S0965542509020055.

He J., Verstak A., Watson L., Sosonkina M. Design and implementation of a massively parallel version of DIRECT. Comput. Optim. Appl. 2008. Vol. 40, no. 2. P. 217–245. DOI: 10.1007/s10589-007-9092-2.

Paulavicius R., Žilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds. Optim. Method. Softw. 2011. Vol. 26, no. 3. P. 487–498. DOI: 10.1080/10556788.2010.551537.

Strongin R.G., Sergeyev Y.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000. DOI: 10.1007/978-1-4615-4677-1.

Hooke R., Jeeves T. “Direct Search” Solution of Numerical and Statistical Problems. J. ACM. 1961. Vol. 8, no. 2. P. 212–229. DOI: 10.1145/321062.321069.

Nocedal J., Wright S. Numerical Optimization. New York: Springer, 2006. DOI: 10.1007/b98874.

Kelley C.T. Iterative Methods for Optimization. Philadelphia: SIAM, 1999. DOI: 10.1137/1.9781611970920.

Barkalov K., Lebedev I. Solving multidimensional global optimization problems using graphics accelerators. Communications in Computer and Information Science. 2016. Vol. 687. P. 224–235. DOI: 10.1007/978-3-319-55669-7_18.

Barkalov K., Strongin R. A global optimization technique with an adaptive order of checking for constraints. Computational Mathematics and Mathematical Physics. 2002. Vol. 42, no. 9. P. 1289–1300.

Gergel V.P. A global optimization algorithm for multivariate functions with Lipschitzian first derivatives. Journal of Global Optimization. 1997. Vol. 10, no. 3. P. 257–281. DOI: 10.1023/A:1008290629896.

Himmelblau D. Applied Nonlinear Programming. New York: McGraw-Hill, 1972. 498 p.

Brahmbhatt S. Practical OpenCV (Technology in Action). New York: Apress, 2013. DOI: 10.1007/978-1-4302-6080-6_1.

Sergeyev Y., Kvasov D. Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants. SIAM J. Optim. 2006. Vol. 16, no. 3. P. 910–937. DOI: 10.1137/040621132.

Barkalov K., Lebedev I., Kocheganova M., Gergel V. Combining local and global search in a parallel nested optimization scheme. Communications in Computer and Information Science. 2020. Vol. 1263. P. 100–112. DOI: 10.1007/978-3-030-55326-5_8.




DOI: http://dx.doi.org/10.14529/cmse230301