Lipschitz global optimization

Abstract:

Global continuous optimization is a thriving branch of applied mathematics. 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. 

Several adaptive partition methods and strategies for estimating the Lipschitz constant 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.