Global Optimization in Action

A review of the book

János D. Pintér,
Global Optimization in Action.
Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications.
Nonconvex Optimization and Its Applications, Vol. 6
Kluwer Academic Publishers, Dordrecht - Boston - London 1996.

(for the Journal of Global Optimization)


The book discusses optimization problems with continuous variables and either a nonconvex objective function or a nonconvex constraint set. These problems often have several local minima, and the task to find the one with the lowest function value is termed global optimization.

The systematic search for methods that solve the global optimization problem probably began in 1975 with Dixon and Szegö [1]. Before this date, researchers in the optimization community regarded the solution of general smooth, nonconvex global optimization problems as being beyond tractability, and the multiple random start heuristic was the only means to try to find better minima.

Of course, there are global optimization problems that are exceptionally hard; among them are problems of high practical significance such as the protein folding problem (see, e.g., Richards [5], Neumaier [4]). For some classes of global optimization problems, even NP-hardness - the mathematical seal for the existence of intractable instances - can be proved (see, e.g., the survey by Vavasis [6]).

However, many problems are much easier than the worst case. János Pintér's book shows how much the picture changed since 1975, and that a wide variety of global optimization problems arising in applications can be successfully treated.

Because of its broad coverage of real-life applications, this book is a welcome complement to other books on global optimization that emphasize theory and techniques (my recommendations for the latter are the collection of surveys in Horst and Pardalos [2] and the book on rigorous global optimization by Kearfott [3]), but are restricted in their examples to simple academic problems.

The contents of the book is split into four parts:

Part I discusses generalities about problem classes and contains a short but useful survey of the various solution techniques known for solving global optimization problems.

Part II then discusses partition strategies for a branch and bound framework, concentrating on theory and techniques involving (global or adaptive) Lipschitz constants. General conditions are found that guarantee convergence of a partition method to the set of global minimizers. The theory is first developed for abstract constraint sets D, then specialized to the case where D is a box, a simplex, a star shaped domain, or a set defined by a family of Lipschitz continuous inequalities.

Part III considers refinements and details of a particular implementation in the author's (commercial) LGO global optimization environment. LGO is designed for problems with up to 50 variables and a limit of 10.000 simultaneously stored boxes. It accepts bound constrained global optimization problems only. For more general constraints, the author advocates the use of penalty functions; however, the adaptation of the penalty multipliers to guarantee convergence to the set of global minimizers is addressed much too briefly to be of practical value, and essentially leaves their choice to the user, who is likely to pick inappropriate values. (The author informed me that some of the limitations of the version described in the book are relaxed in the current version of LGO.)

Since in practice, realistic Lipschitz constants are difficult to obtain (and impossible if only objective function values are available through a black box routine), the estimation of approximate Lipschitz constants using extreme value statistics is discussed in some detail. Of course, using approximate Lipschitz constants of unknown quality implies that convergence to a global minimizer is no longer guaranteed. However, this is not an impediment to practical usefulness: often the global minimizer is nevertheless found, and good local minimizers are already useful even when they are not global.

Part III also contains some sections of quite different flavor, namely how to bring certain stochastic programming problems (only the simpler case without recourse is discussed in detail) within the scope of the treated global optimization methods. This involves the estimation of expectations and probabilities by sample averages, and bounds on the size of the required samples are derived. Unfortunately, these sections are not self-contained, e.g, familiarity with inequalities of Markov and Chebyshev is assumed.

Part IV considers thirteen applications from different areas, mostly from the author's research and consulting practice, proceeding in each case from modeling by a Lipschitz global optimization problem to finding the solution of a sample problem. Some of the problems treated are prototypes for generic classes of problems; examples are finding all solutions of nonlinear systems of equations, unsupervised classification of data (cluster analysis), pooling expert opinions, and model calibration. In the last case, the sample models are related to shallow lake modeling, water pollution transport, and river flow. The other problems are less generic, and involve optimal mixing, nutrient flow in ecological systems, inverse groundwater modeling, industrial wastewater management, river pollution management, lake eutrophication control, and environmental hazard management.

Several of the problems involve the solution of ordinary or partial differential equations to compute function values and/or take account of statistical uncertainties in the model formulation. Many figures make the concepts, models and solutions more intelligible.

An appendix points the reader to more than 130 references with further applications, grouped by the field of application.

In summary, this is a very valuable book for everyone interested in the actual use of global optimization techniques. The broad spectrum of ideas and applications covered, together with the easy-going style make the book also a useful source for a course on global optimization. (There are no exercises in the book, but it is not difficult to design a number of term projects based on the material given.)

Arnold Neumaier


[1] L.C.W. Dixon and G.P. Szegö (eds.),
Towards Global Optimization,
Elsevier, New York 1975.

[2] R. Horst and P.M. Pardalos (eds.),
Handbook of Global Optimization,
Kluwer, Dordrecht 1995.

[3] R.B. Kearfott,
Rigorous Global Search: Continuous Problems,
Kluwer, Boston 1996.

[4] A. Neumaier,
The mathematics of protein folding: a feasibility study of mathematical prediction of protein structure,
SIAM Review, to appear.

[5] F. Richards,
The protein folding problem,
Scientific American 264 (January 1991), 54-63.

[6] S.A. Vavasis,
Complexity issues in global optimization: a survey,
pp. 27-41 in:
R. Horst and P.M. Pardalos (eds.),
Handbook of Global Optimization,
Kluwer, Dordrecht 1995.


Global Optimization
my home page (http://arnold-neumaier.at)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)