Parallel Lipschitz Global Optimization Method

В статье представлен подход к решению задач липшицевой глобальной оптимизации, основной целью которого является ускорение нахождения глобального минимума липшицевой функции за счет использования нескольких параллельных потоков обработки. Алгоритм состоит из двух основных этапов: глобального поиска, во время которого определяются гиперинтервалы (многомерные параллелепипеды), на которых может содержаться глобальный минимум, и локального поиска, где происходит уточнение значения минимума для рассматриваемого гиперинтервала. На этапе глобального поиска используется метод ветвей и границ. Получение нижней оценки минимума функции достигается с помощью оценивания константы Липшица. В статье приведено подробное описание разработанного алгоритма, даны необходимые пояснения, показана корректность разработанного алгоритма. Метод может быть применен к многомерным многоэкстремальным функциям, в том числе, не имеющим аналитического представления, т.е. заданным вформе черного ящика . Простота представленного алгоритма позволяет выполнять оценку константы Липшица параллельно, что, при использовании современных вычислительных систем с многоядерными процессорами может существенно уменьшить время работы программы. Достигаемое благодаря параллельному выполнению ускорение подтверждено серией экспериментов. Методика проведения экспериментов представлена в данной статье, так же, как и пояснения по выбору параметров работы алгоритма. Проведено сравнительное исследование скорости работы алгоритма в последовательном и параллельном режимах, проведен анализ полученных результатов и сделаны выводы об эффективности предложенного подхода. 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 multicore 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.

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.