Global Optimization

Abstract

Global optimization is a field with active research. It is the process of finding the global extremum of a function of n variables, with the possibility of being subjected to some constraints. Its importance is due to the increasing needs in many applications in sci- ences and engineering. Two factors render the global optimization of certain classes of multivariate multi-extremal functions difficult to treat: local irregularity, for example non differentiability and the existence of a large number of local and global extrema of the ob- jective function in the feasible area. One of the key challenges in global optimization is the presence of multiple local optima, which can mislead traditional optimization algorithms into converging to suboptimal solutions. To address this challenge, global optimization algorithms employ various strategies to explore the solution space more thoroughly and efficiently, aiming to find the global optimum or approximate it within a specified tol- erance. During the last recent years, numerous works have been realized concerning Lipschitz functions [5, 6, 10, 14]. More recently, some works tackling less regular functions have appeared [4]. Several techniques are used in global optimization, including: Deterministic methods: These methods systematically explore the solution space to guar- antee convergence to the global optimum under certain conditions. Examples include branch and bound, interval analysis, and outer approximation methods. Stochastic methods: These methods use randomness to explore the solution space, often based on probabilistic principles. Examples include simulated annealing, genetic algo- rithms, particle swarm optimization, and evolutionary algorithms. In this work we will consider only Lipschitz and Holder continuous objective functions of which the Lipschitz and the Holder constants are known. This document is primarily aimed at Master’s students in mathematics specializing in Modeling and Decision Support, as well as any student working on global optimization. Chapter 1 introduces some important terminology and definitions and describes the field of local optimization. Also we give some reminders of optimal conditions for an optimiza- tion problem without constraints, thus some classical approached algorithms to determine the solution of this problem. In chapter 2, we are interested in deterministic global optimization methods. Our atten- tion will be paid to one -dimensional covering methods which have the reputation of being effective in dimension 1. Among these methods, there are those based on the use of linear or non-linear support functions, others on covering the feasible domain. We will finish this chapter with a series of exercises taken from Literature and others proposed by the author. The third chapter is devoted to the extension of certain covering methods to mul-tidimensional cases without and with constraints. Two essential methods were presented. The first method based on a technique for partitioning and eliminating the regions of the feasible set not containing the global minimum known by Branch-And-Bound. A second method is of Alienor reducing transformation, is presented. The main idea in this method consists of approximating the objective function of several variables defined on a compact set C of Rn, by a function of a single variable by densifying the feasible set C using a simple curve . This makes it possible to reduce the multidi- mensional optimization problem to a one-dimensional optimization problem, to be able to use the one-dimensional methods seen in the second chapter. Finally, we will end this chapter with a series of numerical exercises.