Parallel Global Optimization Algorithm for Obtaining Uniform Convergence When Simultaneously Solving a Set of Global Optimization Problems
DOI:
https://doi.org/10.14529/cmse200201Keywords:
global optimization, parallel computations, derivative-free optimization, uniform convergenceAbstract
In this work building of a parallel version of a method simultaneously solving a set of constrained global optimization problems is considered. This method converges uniformly to solutions of all the problems. That allows the method to arrange computational resources in an optimal way, since uniform convergence guarantees approximately equal precision of numerical solutions at the whole set of problems at the each iteration of optimization. The algorithm assigns a priority to each problem, and then at the each iteration carries out calculation of objective functions and constraints in several problems in parallel. If the method stops at any arbitrary moment, in all the problems numerical sulutions with the similar accuracy will be obtained. Sets of similar global optimization problems appear for an instance after scalarization of multi-objective problems or when a global optimization problem has a discrete parameter which takes a finite number of possible values. The considered method uses Peano-type curves to transform multidimensional problems into univariate ones. Efficiency of the implemented parallel algorithm is evaluated on several sets of synthetically generated constrained global optimization problems and on a scalarized multi-objective problem. Also the uniform convergence was confirmed numerically by validation quality of intermediate solutions during the optimization process.
References
Barkalov K., Lebedev I. Comparing two approaches for solving constrained global optimization problems. Learning and Intelligent Optimization (Nizhny Novgorod, Russia, June, 19–21, 2017). Springer International Publishing, Cham. 2017. P. 301–306. DOI: 10.1007/978-3-319-69404-7_22.
Barkalov K., Lebedev I. Parallel algorithm for solving constrained global optimization problems. Parallel Computing Technologies (Nizhni Novgorod, Russia, Sept., 4–8, 2017). Springer International Publishing, Cham. 2017. P. 396–404. DOI: 10.1007/978-3-319-62932-2_38.
Barkalov K., Strongin R. Solving a set of global optimization problems by the parallel technique with uniform convergence. Journal of Global Optimization. 2018. Vol. 71, no. 1. P. 21–36. DOI: 10.1007/s10898-017-0555-4.
Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms. Optimization and Engineering. 2017. Vol. 18, no. 4. P. 815–848. DOI: 10.1007/s11081-017-9366-1.
Ehrgott M. Multicriteria Optimization. Springer-Verlag, Berlin, Heidelberg, 2005. 323 p. DOI: 10.1007/3-540-27659-9.
Evtushenko Y., Posypkin M. A deterministic approach to global box-constrained optimization. Optimization Letters. 2013. Vol. 7. P. 819–829. DOI: 10.1007/s11590-012-0452-1.
Gaviano M., Kvasov D.E., Lera D., Sergeev Ya.D. Software for generation of classes of test functions with known local and global minima for global optimization. ACM Transactions on Mathematical Software. 2003. Vol. 29, no. 4. P. 469–480. DOI: 10.1145/962437.962444.
Gergel V., Barkalov K., Lebedev I., Rachinskaya M., Sysoyev A. A flexible generator of constrained global optimization test problems. AIP Conference Proceedings. 2019. Vol. 2070, no. 1. P. 020009. DOI: 10.1063/1.5089976.
Jones D.R. The direct global optimization algorithm. The Encyclopedia of Optimization. Springer, Heidelberg. 2009. P. 725–735. DOI: 10.1007/978-0-387-74759-0_128.
Paulavivcius R., Zilinskas J., Grothey A. Parallel branch and bound for global optimization with combination of Lipschitz bounds. Optimization Methods and Software. 1997. Vol. 26, no. 3. P. 487–498. DOI: 10.1080/10556788.2010.551537.
Riquelme N., Von Lucken C., Baran B. Performance metrics in multi-objective optimization. 2015 Latin American Computing Conference (Arequipa, Peru, Oct., 19–23, 2015). IEEE. 2015. P. 1–11. DOI: 10.1109/clei.2015.7360024.
Sergeyev Y., Kvasov D. Deterministic Global Optimization. Springer, New York, 2017. 136 p. DOI: 10.1007/978-1-4939-7199-2.
Sergeyev Y.D., Strongin R.G., Lera D. Introduction to global optimization exploiting space-filling curves. Springer Briefs in Optimization, Springer, New York, 2013. 125 p. DOI: 10.1007/978-1-4614-8042-6.
Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000. 704 p. DOI: 10.1007/978-1-4615-4677-1.
To T.B., Korn B. MOBES: A multiobjective evolution strategy for constrained optimization problems. Proceedings of the 3rd international conference on genetic algorithms (Mendel 97). 1997. P. 176–182.
Grishagin V. Operating characteristics of some global search algorithms. Problems of Stochastic Search. 1978. no. 7. P. 198–206. (in Russian)
Norkin V. I. Towards Pijavskyj’s method for solving common global optimization problem. Computational Mathematics and Mathematical Physics. 1992. Vol. 32, no. 7. P. 992–1006. (in Russian)
