# 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.

• Combinatorial problems have a linear or nonlinear function defined over a set of solutions that is finite but very large. There are a number of significant categories of combinatorial optimization problems, including network problems, scheduling, and transportation. If the function is piecewise linear, the combinatorial problem can be solved exactly with a mixed integer program method, which uses branch and bound. Heuristic methods like simulated annealing, tabu search and genetic algorithms have also been successfully applied to these problems to find approximate solutions.
• General unconstrained problems have a nonlinear function over reals that is unconstrained (or which have simple bound constraints). A variety of partitioning strategies have been proposed to solve this problem exactly. These methods typically rely on a priori knowledge of how rapidly the function can vary (e.g. the Lipshitz constant) or the availability of an analytic formulation of the objective function (e.g. interval methods). Statistical methods also use partitioning to decompose the search space, but they use a priori information (or assumptions) about how the objective function can be modeled. A wide variety of other methods have been proposed for solving these problems inexactly, including simulated annealing, genetic algorithms, clustering methods, and continuation methods, which first transform the potential function into a smoother function with fewer local minimizers, and then uses a local minimization procedure to trace the minimizers back to the original function (e.g., Moré and Wu).
• General constrained problems have a nonlinear function over reals that is constrained. These types of problems have not received as much attention as have general unconstrained problems. However, many of the methods for unconstrained problems have been adapted to handle constraints.
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