B o o k Review

Horst R, Tuy H: Global Optimization. Deterministic Approaches. SpringerVerlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, Hong Kong (ISBN 3-540-52368-5 resp. 0-387-52368-5), 1990, XIV+696 pp, DM220,In this book Reiner Horst and Hoang Tuy systematically derive the diverse deterministic approaches to the solution of multiextremal global optimization problems and apply them to a variety of problems of general interest. The problems which for the time being can be solved by these techniques and which are studied in the book are (a) the minimization of concave functions subject to linear and convex constraints ("concave minimization"), (b) the convex minimization over the intersection of convex sets and complements of convex sets ("reverse convex programming"), (c) the global optimization of functions that can be expressed as a difference of two convex functions ("d.c.-programming"), and (d) the minimization of problems where the functions in the formulation are Lipschitz continuous with computable Lipschitz constants ("Lipschitz programming"). The authors, who themselves have done pioneering work in this field, summarize and extend an impressing amount of material in a unifying and clarifying way and so give a comprehensive representation of the state of the art of an important and rapidly growing area in applied mathematics. The book is divided into three main parts. Part A (Chapters I - I V ) gives the "Introduction and Basic Techniques". In Chapter I ("Some Important Classes of Global Optimization Problems") the above listed classes of optimization problems are introduced and motivated by an enormous number of references to economical, engineering and mathematical applications. In Chapters II, III and IV the basic solution techniques of deterministic global optimization are developed: "Outer Approximation", "Concavity Cuts" and "Branch and Bound". In these chapters the reader is carefully and slowly led from the geometric ideas behind these techniques to unifying abstract settings of them. Summarizing, Part A of the book shows the present applications and the characteristics of global optimization and contains the basic tools for the convergence proofs of the algorithms in the later sections. Besides it includes a beautiful representation of some well-known optimization methods as, for example, cutting methods and hence can be recommended to anyone being interested in optimization theory. Part B (consisting of Chapters V-IX) is devoted to "Concave Minimization". In Chapters V, VI and VII particular solution methods, named "Cutting Methods", "Successive Approximation Methods" and "Successive Partition Methods", are investigated. Chapter VIII ("Decomposition of Large Scale Problems") and Chapter IX ("Special Problems of Concave Optimization") deal with special concave problems. These are problems, where the objective function is the sum of a concave part and of a linear part involving most of the variables, respectively problems of a special form including bilinear programming problems, complementarity problems and certain parametric problems as linear programming problems with an additional reverse convex constraint.

478

Book Review

Part C (Chapters X and XI) finally is concerned with more "General Nonlinear Problems". In Chapter X ("D.C. Programming") outer approximation and branch and bound methods are discussed for the so-called design centering problem and for quite general d.c. problems including examples of functions whose d.c. representation is not known. The book concludes in Chapter XI ("Lipschitz and Continuous Optimization") with global optimization methods for the solution of Lipschitz programming problems. As an example the problem of minimizing a concave function subject to separable indefinite quadratic constraints is considered in some detail. Also in Parts B and C the reader is guided in an elucidating way from the geometrical and abstract concepts behind the specific algorithms to their often lengthy and complicated formal descriptions. Besides he obtains a survey of the historical development of the field and he can simultaneously enjoy the unifying approach of the authors to the large number of methods to which they refer. "Preliminary" numerical results are given occasionally. Concerning the implementation of the algorithms, the reader is fairly informed about numerical aspects and limits. The book is clearly written and lucidly structured. In particular, the used notions are thoroughly defined, the diverse ideas are well explained, and the results are beautifully motivated. The didactically skillful and stimulating presentation of the material is supported by the excellent get-up of the book by the publishers which somewhat soothes the pain caused by its high price. It is a pleasure to read this book which undoubtedly is an essential contribution in applied mathematics and which will become a standard reference not only in the field of optimization theory. R. Reemtsen

Berlin

Software Review

CATBOX-Combinatorial Algorithms Toolbox (Version 2.0), Mathematisches Institut der Universit~t zu KOln, Prof. Dr. A. Bachem, Dipl.-Math. Th. Effing, 1990 CATBOX is a package of combinatorial optimization algorithms implemented using Turbo Pascal. In the words of the author, the main purpose is "not speed but the visualization of the ideas of combinatorial algorithms (interactively on the computer)". To install CATBOX, one requires a PC AT using DOS 3.x, at least 540 KB free RAM, a coprocessor (80287/80387), together with several megabytes of hard disc space. The requirements on the disk storage can be reduced if one only implements a subset of the available algorithms. Moreover, an EGA- or a VGA-monitor (640• resolution) is necessary for the graphics.