Preface to the First Edition
This book grew out of lecture notes from a course given at Graz University of
Technology (autumn 1990), The Institute of Technology at Linköping University
(autumn 1991), and the Ecole Polytechnique in Montréal (autumn 1993). Originally
conceived of as a Ph.D. course, it attempts to present a coherent and mathematically
rigorous theory of deterministic global optimization. At the same time, aiming at
providing a concise account of the methods and algorithms, it focuses on the main
ideas and concepts, leaving aside too technical details which might affect the clarity
of presentation.
Global optimization is concerned with finding global solutions to nonconvex
optimization problems. Although until recently convex analysis has been developed
mainly under the impulse of convex and local optimization, it has become a basic
tool for global optimization. The reason is that the general mathematical structure
underlying virtually every nonconvex optimization problem can be described in
terms of functions representable as differences of convex functions (dc functions)
and sets which are differences of convex sets (dc sets). Due to this fact, many
concepts and results from convex analysis play an essential role in the investigation
of important classes of global optimization problems. Since, however, convexity
in nonconvex optimization problems is present only partially or in the “other”
way, new concepts have to be introduced and new questions have to be answered.
Therefore, a new chapter on dc functions and dc sets is added to the traditional
material of convex analysis. Part I of this book is an introduction to convex analysis
interpreted in this broad sense as an indispensable tool for global optimization.
Part II presents a theory of deterministic global optimization which heavily relies
on the dc structure of nonconvex optimization problems. The key subproblem in
this approach is to transcend an incumbent, i.e., given a solution of an optimization
problem (the best so far obtained), check its global optimality, and find a better
solution, if there is one. As it turns out, this subproblem can always be reduced to
solving a dc inclusion of the form x 2 D n C; where D; C are two convex sets.
Chapters 4–6 are devoted to general methods for solving concave and dc programs
through dc inclusions of this form. These methods include successive partitioning
and cutting, outer approximation and polyhedral annexation, or combination of the
v
