Introduction to Global Optimization

Global Search, As Timely As Ever

``Consider everything. Keep the good. Avoid evil whenever you notice it.''
(1 Thess. 5:21-22)

This file is part of my global optimization web site.

Global optimization is the task of finding the absolutely best set of admissible conditions to achieve your objective, formulated in mathematical terms. It is the hardest part of a subject called nonlinear programming (NLP). See, e.g., the Mathematical Programming Glossary, the WORMS Topics Directory on Optimization and Operations Research, or the Nonlinear Programming FAQ. [Widen your horizon and discover another interesting but quite different meaning of the acronym NLP.]

For finding only locally optimal solutions, which is considerably easier, specific recommendations on (mostly) public domain software can be found in the Decision Tree for Optimization Software. Both public domain and commercial codes are listed in the NEOS Guide to Optimization Software. Some pointers are also given in our section on Local Optimization Software.

A basic reference on most aspects of global optimization until 1995 is the recent book

R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer, Dordrecht 1995.
It contains chapters written by the experts in the respective subfields, on global optimality conditions, complexity issues, concave minimization, dc methods, indefinite quadratic programming, complementarity problems, minimax problems, multiplicative programming, Lipschitz optimization, fractional programming, network problems, continuation methods, interval methods, and stochastic methods (including simulated annealing).

The editors are (like myself) proponents of complete methods; this may explain why some techniques that are useful at the present stage of knowledge are not discussed. This applies, e.g., to heuristic techniques like tunneling, tabu search, threshold accepting. A major omission is the lack of discussion of genetic algorithms; for this topic, look instead into

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed., Springer, Berlin 1996.

Some more recent books present complete global optimization from two perspectives: The interval point of view is in

The convex analysis point of view is in
and (taylored towards the BARON global optimization package)
The November 2003 state of the art in complete global optimization is described in A group of people from Sandia National Laboratories wrote a thorough Survey of Global Optimization Methods from a different perspective. Aimo Törn's site Global Optimization contains an excellent exposition of stochastic global optimization methods for bound constrained problems. Baker Kearfott has an essay What Is Global Optimization? that emphasizes the interval approach to global optimization.

Janos Pinter has an interesting online paper on Continuous Global Optimization: An Introduction to Models, Solution Approaches, Tests and Applications.

A good source on information about heuristic global optimization methods for combinatorial problems is

E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization, Wiley, Chichester 1997.

Real world applications of global optimization are extensively treated in the book

Janos D. Pinter, Global Optimization in Action, Kluwer, Dordrecht 1996;
see my review. For online applications (but mostly involving local optimization only), look at some Examples and Case Studies in Optimization.

Univariate global optimization is fairly simple because the curse of dimensionality does not yet apply and there is a natural linear ordering of the arguments. Most other classes of global optimization problems are NP-hard, however. This implies that (unless P=NP), for each algorithm, there are always some instances that take more than polynomial time in the length of the input data. See, e.g., A compendium of NP optimization problems (by Crescenzi and Kann)

SIAM maintains a collection of Optimization Books and Proceedings on local (and some global) optimization, and there are also some other Global Optimization Books.

For other topics related to optimization, you might find something at the following links:

Mathematical Optimization Society (formerly Mathematical Programming Society)

Some of My Other Pages

Global (and Local) Optimization Mathematics Links