Parallel Lipschitz Global Optimization Method
Abstract
The article is devoted to the description of the developed approach for solving Lipschitz global optimization problems. The main goal of the proposed approach is to accelerate the search for a global minimum of the Lipschitz function through the use of several parallel processing threads. The algorithm consists of two phases: the global search phase, which specifies the hyperintervals (multidimensional parallelepipeds), which may contain a global minimum, and the local search phase, where the minimum value for the hyperinterval is refined. The global search phase uses the branch and bound method. The calculation of the lower estimate of the minimum of a function is performed by estimating the Lipschitz constant. The article describes the developed algorithm, gives the necessary explanations, and shows the correctness of the developed algorithm. The method can be applied to multidimensional multiextremal functions, including those that do not have an analytical representation, i.e. specified in the form of a "black box". The simplicity of the developed algorithm makes it possible to estimate the Lipschitz constant in parallel, which, in case of using modern computing systems with multi-core processors, can significantly speed up the execution of the program. The acceleration achieved due to parallel execution is confirmed by a series of experiments. The methodology of the experiments provided in this article, as well as explanations for the choice of the parameters of the algorithm. A comparative study of the speed of the algorithm in sequential and parallel modes was carried out, obtained results were analyzed and conclusions were made about the effectiveness of the proposed approach.
References
[2] Strongin R.G., Sergeyev Y.D. Global optimization with non-convex constraints: Sequential and parallel algorithms. Nonconvex Optimization and Its Applications. Springer, Boston, MA. 2013; 45. (In Eng.) DOI: 10.1007/978-1-4615-4677-1
[3] Sergeyev Y.D., Kvasov D.E. Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM Journal on Optimization. 2006; 16(3):910-937. (In Eng.) DOI: 0.1137/040621132
[4] Sergeyev Y.D., Strongin R.G., Lera D. Introduction to Global Optimization Exploiting Space-Filling Curves. SpringerBriefs in Optimization. Springer, New York, NY, 2013. (In Eng.) DOI: 10.1007/978-1-4614-8042-6
[5] Hansen P., Jaumard B. Lipschitz optimization. Handbook of global optimization. Springer, Boston, MA. 1995; 407-493. (In Eng.) DOI: 10.1007/978-1-4615-2025-2
[6] Paulavičius R., Žilinskas J. Simplicial Lipschitz optimization without Lipschitz constant. In: Paulavičius R., Žilinskas J. (eds). Simplicial Global Optimization. Springer, New York, NY. 2014; 61-86. (In Eng.) DOI: 10.1007/978-1-4614-9093-7
[7] Evtushenko Yu.G. Numerical methods for finding global extrema (Case of a non-uniform mesh). USSR Computational Mathematics and Mathematical Physics. 1971; 11(6):38-54. (In Eng.) DOI: 10.1016/0041-5553(71)90065-6
[8] Chandra R. et al. Parallel programming in OpenMP. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001. (In Eng.)
[9] Sato M. OpenMP: parallel programming API for shared memory multiprocessors and on-chip multiprocessors. 15th International Symposium on System Synthesis. Kyoto, Japan. 2002; 109-111. (In Eng.) DOI: 10.1145/581199.581224
[10] Williams A. C++ concurrency in action. Manning Publications Co., 2019. (In Eng.)
[11] Evtushenko Y., Posypkin M. A deterministic approach to global box-constrained optimization. Optimization Letters. 2013; 7(4):819-829. (In Eng.) DOI: 10.1007/s11590-012-0452-1
[12] Evtushenko Y.G., Posypkin M.A. A deterministic algorithm for global multi-objective optimization. Optimization Methods and Software. 2014; 29(5):1005-1019. (In Eng.) DOI: 10.1080/10556788.2013.854357
[13] Evtushenko Y.G., Posypkin M.A. An application of the nonuniform covering method to global optimization of mixed integer nonlinear problems. Computational Mathematics and Mathematical Physics. 2011; 51(8):1286. (In Eng.) DOI: 10.1134/S0965542511080082
[14] Evtushenko Y.G., Posypkin M.A. Nonuniform covering method as applied to multicriteria optimization problems with guaranteed accuracy. Computational Mathematics and Mathematical Physics. 2013; 53(2):144-157. (In Eng.) DOI: 10.1134/S0965542513020061
[15] Evtushenko Y., Posypkin M., Sigal I. A framework for parallel large-scale global optimization. Computer Science-Research and Development. 2009; 23(3-4):211-215. (In Eng.) DOI: 10.1007/s00450-009-0083-7
[16] Barkalov K., Gergel V. Parallel global optimization on GPU. Journal of Global Optimization. 2016; 66(1):3-20. (In Eng.) DOI: 10.1007/s10898-016-0411-y
[17] Haftka R.T., Villanueva D., Chaudhuri A. Parallel surrogate-assisted global optimization with expensive functions–a survey. Structural and Multidisciplinary Optimization. 2016; 54(1):3-13. (In Eng.) DOI: 10.1007/s00158-016-1432-3
[18] Barkalov K., Gergel V., Lebedev I. Use of xeon phi coprocessor for solving global optimization problems. International Conference on Parallel Computing Technologies. Springer, Cham. 2015; 307-318. (In Eng.) DOI: 10.1007/978-3-319-21909-7_31
[19] Ferreiro A. M. et al. Parallel two-phase methods for global optimization on GPU. Mathematics and Computers in Simulation. 2019; 156:67-90. (In Eng.) DOI: 10.1016/j.matcom.2018.06.005
[20] Strongin R.G. et al. Generalized Parallel Computational Schemes for Time-Consuming Global Optimization. Lobachevskii Journal of Mathematics. 2018; 39(4):576-586. (In Eng.) DOI: 10.1134/S1995080218040133
[21] Zhang G.W. et al. Parallel particle swarm optimization using message passing interface. Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems. Springer, Cham. 2015; 1:55-64. (In Eng.) DOI: 10.1007/978-3-319-13359-1_5
[22] Popov M.V., Posypkin M.A. Effective Realization of Exact Algorithms for Solving Discrete Optimization Problems on Graphic Accelerators. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2018; 14(2):408-418. (In Russ., abstract in Eng.) DOI: 10.25559/SITITO.14.201802.408-418
[23] Gorchakov A.Y. Posypkin M.A. Comparison of variants of multithreading realization of method of branches and borders for multi-core systems. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2018; 14(1):138-148. (In Russ., abstract in Eng.) DOI: 10.25559/SITITO.14.201801.138-148
[24] Gaviano M., Kvasov D.E., Lera D., Sergeyev Y.D. Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Transactions on Mathematical Software. 2003; 29(4):469-480. (In Eng.) DOI: 10.1145/962437.962444
[25] Posypkin M., Usov A. Implementation and verification of global optimization benchmark problems. Open Engineering. 2017; 7(1):470-478. (In Eng.) DOI: 10.1515/eng-2017-0050
[26] Gorchakov A.Y. Posypkin M.A. The effectiveness of local search methods in the problem of finding the minimum energy of a 2-d crystal. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2017; 13(2):97-102. (In Russ., abstract in Eng.) DOI: 10.25559/SITITO.2017.2.247
[27] Evtushenko Y.G., Lurie S.A., Posypkin M.A., Solyaev Yu.O. Application of optimization methods for finding equilibrium states of two-dimensional crystals. Computational Mathematics and Mathematical Physics. 2016; 56(12):2001–2010. (In Eng.) DOI: 10.1134/S0965542516120083
[28] Posypkin M. Automated Robot’s Workspace Approximation. Journal of Physics: Conference Series. 2019; 1163(1):012050. (In Eng.) DOI: 10.1088/1742-6596/1163/1/012050
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
