LIPSCHITZ GLOBAL OPTIMIZATION
Yaroslav D. Sergeyev, Ph.D., D.Sc., D.H.C.
Distinguished Professor, Head of Numerical Calculus Laboratory
Calabria University, Rende (CS), Italy
Professor, Lobachevsky University of Nizhni Novgorod, Russia
Abstract: Global optimization is a thriving branch of applied mathematics and an extensive literature is dedicated to it. In this lecture, the global optimization problem of a multidimensional function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. It is supposed that the objective function can be ``black box", multiextremal, and non-differentiable. It is also assumed that evaluation of the objective function at a point is a time-consuming operation. Many algorithms for solving this problem have been discussed in the literature. They can be distinguished, for example, by the way of obtaining information about the Lipschitz constant and by the strategy of exploration of the search domain. Different exploration techniques based on various adaptive partition strategies are analyzed.
The main attention is dedicated to two types of algorithms. The first of them is based on using space-filling curves in global optimization. A family of derivative-free numerical algorithms applying space-filling curves to reduce the dimensionality of the global optimization problem is discussed. A number of unconventional ideas, such as adaptive strategies for estimating Lipschitz constant, balancing global and local information to accelerate the search, etc. are presented. Diagonal global optimization algorithms is the second type of methods under consideration. They have a number of attractive theoretical properties and have proved to be efficient in solving applied problems. In these algorithms, the search hyperinterval is adaptively partitioned into smaller hyperintervals and the objective function is evaluated only at two vertices corresponding to the main diagonal of the generated hyperintervals. It is demonstrated that the traditional diagonal partition strategies do not fulfil the requirements of computational efficiency because of executing many redundant evaluations of the objective function. A new adaptive diagonal partition strategy that allows one to avoid such computational redundancy is described. Some powerful multidimensional global optimization algorithms based on the new strategy are introduced. Extensive numerical experiments are performed on the GKLS-generator that is used nowadays in more than 40 countries in the world to test numerical methods. Results of the tests demonstrate that proposed methods outperform their competitors in terms of both number of trials of the objective function and qualitative analysis of the search domain, which is characterized by the number of generated hyperintervals.
1. Ya.D. Sergeyev, D.E. Kvasov, M.S. Mukhametzhanov, On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget, Nature Scientific Reports, 2018, 8:453, DOI:10.1038/s41598-017-18940-4.
2. Ya.D. Sergeyev, D.E. Kvasov, Deterministic global optimization: An introduction to the diagonal approach, Springer, New York, 2017.
3. R.G. Strongin and Ya.D. Sergeyev, Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms, Springer, New York, 3rd ed., 2014.
4. Ya.D. Sergeyev, R.G. Strongin, and D. Lera, Introduction to Global Optimization Exploiting Space-Filling Curves, Springer, New York, 2013.
Biography: Yaroslav D. Sergeyev, Ph.D., D.Sc., D.H.C. is Distinguished Professor at the University of Calabria, Italy and Head of Numerical Calculus Laboratory at the same university. His research interests include numerical analysis, global optimization (since 2017 he is President of the International Society of Global Optimization), infinity computing and calculus, philosophy of computations, set theory, number theory, fractals, parallel computing, and interval analysis. Prof. Sergeyev was awarded several research prizes (Khwarizmi International Award, 2017; Pythagoras International Prize in Mathematics, Italy, 2010; EUROPT Fellow, 2016; Outstanding Achievement Award from the 2015 World Congress in Computer Science, Computer Engineering, and Applied Computing, USA; Honorary Fellowship, the highest distinction of the European Society of Computational Methods in Sciences, Engineering and Technology, 2015; The 2015 Journal of Global Optimization (Springer) Best Paper Award; Lagrange Lecture, Turin University, Italy, 2010; MAIK Prize for the best scientific monograph published in Russian, Moscow, 2008, etc.).
His list of publications contains more than 250 items (among them 6 books). He is a member of editorial boards of 8 international journals and co-editor of 11 special issues. He delivered more than 60 plenary and keynote lectures at prestigious international congresses. He was Chairman of 9 international conferences and a member of Scientific Committees of more than 70 international congresses.