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.

Keywords

• global optimization
• lipschitz constant
• parallel programming