The field of global optimization (GO) considers the optimization of an objective function f in a subset S of the real numbers called a feasible region. Since the conversion of maximization problems into minimization problems is straightforward, the GO problem can be considered to deal with solving the minimization of f in the set S. This generally stated problem class has several variants, and a huge amount of research regarding solving this kind of problem has been done over the years with increasing frequency. This book gives a systematic overview covering many different research aspects of GO. It assumes that the function f is continuous and also multimodal over S, which means that f has local minima that are not global ones. To present the problem topic GO within one volume, the authors had to select appropriate material from the huge amount of research; being active researchers within the GO community themselves, they did this from their own research perspectives. This led to six chapters on theoretical as well as practical and algorithmic aspects.
After a brief six-page introduction, chapter 2 deals with the theoretical consideration of complexity, covering basic definitions and their application to the GO problem. Different subclasses of the main problem class differing in the objective function and/or the feasible region are identified. The chapter gives some indication as to whether exact methods can be applied, approximation can be exploited, and heuristics without guarantee about the quality of the returned solution should be used. Heuristic methods are covered in chapter 3, which differentiates between GO problems with objective functions that are cheap to evaluate and those that are costly to evaluate. For each heuristic, basic principles and some bibliographical hints are given. Also, convergence results of the heuristics are stated in the last section of the chapter.
Chapter 4 is dedicated to the computation of lower bounds for the GO problem, which is important to provide as a measure of quality of heuristically detected solutions. Exact methods for solving the GO problem are mostly branch and bound algorithms, which are covered in chapter 5. Starting with a general branch and bound algorithm, different specific implementations from the literature are discussed. One of the implementation steps, the lower bound computation, was already introduced in the previous chapter. The implementation step branching is described in a separate section. Chapter 6 is devoted to applications, starting with general remarks on tests and benchmarks. In addition, four specific problems are described, including molecular conformation, distance geometry, packing, and space trajectory planning.
Although this book on GO problems is presented in a formal and mathematically concise way, it is intended for theoreticians as well as for practitioners seeking solution methods for their own GO problems. The intended audience includes researchers, practitioners, and PhD students. An appendix gives basic mathematical definitions so that the book is self-contained. However, it is not meant to be a course textbook or used for self-study, and no exercises are given. The material can be used for a more advanced course or seminar on optimization.