Introduction to Global Optimization


Global optimization is the task of finding the absolutely best set of parameters to optimize an objective function. In general, there can solutions that are locally optimal but not globally optimal. Consequently, global optimization problems are typically quite difficult to solve exactly; in the context of combinatorial problems, they are often NP-hard. Global optimization problems fall within the broader class of nonlinear programming (NLP). See, e.g., the Mathematical Programming Glossary or the Nonlinear Programming FAQ.

Methods for global optimization problems can be categorized based on the properties of the problem that are used and the types of guarantees that the methods provide for the final solution. A NLP has the form

    minimize   F(x)
    subject to g (x)  = 0     for i=1,...,m1       where m1 >= 0
                i
               h (x) >= 0    for j=m1+1,...,m      where m >= m1
                j
where F is a function of a vector of reals x that is subject to equality and inequality constraints. Some of the most important classes of global optimization problems are differential convex optimization, complementary problems, minimax problems, binlinear and biconvex programming, continuous global optimization and quadratic programming (see the review by Pinter for further details).

Specific optimization methods have been developed for many classes of global optimization problems. Additionally, general techniques have been developed that appear to have applicability to a wide range of problems.

Pinter provides a recent review of global optimization software, and global optimization software is included in A List of Interesting Optimization Software. For specific recommendations on software for finding only locally optimal solutions see the Decision Tree for Optimization Software or the NEOS Guide to Optimization Software. The Nonlinear Programming FAQ provides a nice background on general nonlinear optimization. The Mathematical Programming Glossary provides definitions of a wide range of optimization problems and methods.

References and Related Web Links

R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer, Dordrecht 1995.
An up-to-date reference on most aspects of global optimization with an editorial bias towards deterministic methods.

Janos D. Pinter, Global Optimization in Action Kluwer, Dordrecht 1995.
A collection of real world applications of global optimization.

The global (and local) optimization web page is one of the most complete collections of global optimization links available.

Mike Trick's Operations Research Page provides useful information on many combinatorial optimization problems.

The Sandia Optimization Web Page provides links to optimization research at Sandia National Laboratories.

News/Professional Groups

Journals
Global Optimization Survey - Main Page
Sandia National Laboratories

This page maintained by wehart@cs.sandia.gov
Last modified: March 10, 1997