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