Параллельный метод липшицевой глобальной оптимизации
Аннотация
В статье представлен подход к решению задач липшицевой глобальной оптимизации, основной целью которого является ускорение нахождения глобального минимума липшицевой функции за счет использования нескольких параллельных потоков обработки. Алгоритм состоит из двух основных этапов: глобального поиска, во время которого определяются гиперинтервалы (многомерные параллелепипеды), на которых может содержаться глобальный минимум, и локального поиска, где происходит уточнение значения минимума для рассматриваемого гиперинтервала. На этапе глобального поиска используется метод ветвей и границ. Получение нижней оценки минимума функции достигается с помощью оценивания константы Липшица. В статье приведено подробное описание разработанного алгоритма, даны необходимые пояснения, показана корректность разработанного алгоритма. Метод может быть применен к многомерным многоэкстремальным функциям, в том числе, не имеющим аналитического представления, т.е. заданным в форме «черного ящика». Простота представленного алгоритма позволяет выполнять оценку константы Липшица параллельно, что, при использовании современных вычислительных систем с многоядерными процессорами может существенно уменьшить время работы программы. Достигаемое благодаря параллельному выполнению ускорение подтверждено серией экспериментов. Методика проведения экспериментов представлена в данной статье, так же, как и пояснения по выбору параметров работы алгоритма. Проведено сравнительное исследование скорости работы алгоритма в последовательном и параллельном режимах, проведен анализ полученных результатов и сделаны выводы об эффективности предложенного подхода.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
