Global optimization. Deterministic approaches. (English) Zbl 0704.90057

Horst, Reiner; Tuy, Hoang

Berlin etc.: Springer-Verlag. xiv, 696 p. DM 220.00/hbk (1990).

The goal of this extensive monograph is to give a coherent presentation of algorithms elaborated in recent years for solving global optimization problems. A global optimization problem is defined as follows: given a nonempty set \(A\subset {\mathbb{R}}^ n\), a function f: \(A\to {\mathbb{R}}\), and a set \(D\subset A\), find at least one point \(x^*\in D\) satisfying \(f(x^*)\leq f(x)\) for all \(x\in D\) or show that such a point does not exist. In most cases the feasible set D is determined by a system of inequalities and equalities. Usually the standard nonlinear programming techniques are not applicable to solve the global optimization problems because they yield at most local minima and, in general, local minimizers are not global solutions. For these reasons the specific methods excellently described in the present book are of great interest to everyone seeking solutions of global optimization problems.
The book is divided into eleven chapters, which are arranged in three parts. Part A consists of four chapters. In Chapter I the main classes of global optimization problems that will be studied in the book are introduced: concave minimization, minimization problems involving functions which can be expressed as a difference of two convex functions (d.c. programming problems), and Lipschitzian optimization. Furthermore, some basic properties of these problems and various applications are discussed. In Chapter II the authors present a large class of methods which are among the basic tools in many fields of optimization and which are used in many variants. In these methods, called outer approximation or relaxation methods, the feasible set is approximated from the outside by a sequence of nested sets. This technique is most successfull when the feasible set is convex. Nevertheless, it is adaptable for nonconvex objective functions or nonconvex constraints as shown by the authors in the next chapter, in which they discuss the so-called concavity cuts and use these in cutting procedures. The last chapter of Part A is devoted to the branch and bound methods, in which the feasible set is relaxed and subsequently split into parts over which lower (and often also upper) bounds of the objective function values can be determined.
Part B includes the Chapters V-IX and deals with methods for solving concave minimization problems. The methods described in the Chapters V- VII refer to minimizing an arbitrary concave function over a polyhedron or subject to a convex constraint as well as to minimizing a concave quadratic function over a polyhedron. These methods fall into three main categories: cutting methods, successive approximation methods, and successive partition methods. Chapter VIII is devoted to algorithms for finding global minimizers over a polyhedron of functions which are the sum of two parts: a linear part involving most of the variables of the problem and a concave part involving only a relatively small number of variables. Other special concave minimization problems are studied in Chapter IX. It is shown that many optimization problems (e.g. the bilinear programming problem, the concave complementarity problem, the parametric concave programming problem) can be reduced to concave minimization problems of a special form and solved by specialized concave minimization methods.
In Part C, built up from the Chapters X and XI, very general global optimization problems are considered. Several outer approximation algorithms, branch and bound procedures and combinations thereof are developed for solving d.c. programming and Lipschitzian optimization problems. Among the applications given in this part of the book are design centering problems, biconvex programming problems, and optimization of concave functions subject to separable quadratic constraints.
Based on an extensive bibliography, the present book provides an up-to- date treatment of global solution methods, leading up to the latest developments concerning these methods. It can serve as a valuable reference work for all researchers in this area and for all practitioners interested in solving global optimization problems.

Reviewer: W.Breckner

MSC:

90C30	Nonlinear programming
65K05	Numerical mathematical programming methods
90C26	Nonconvex programming, global optimization
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C31	Sensitivity, stability, parametric optimization

Keywords:

global optimization; d.c. programming; Lipschitzian optimization; outer approximation; relaxation; concavity cuts; cutting methods; successive approximation; successive partition; bilinear programming