Pattern search (optimization)
Encyclopedia
Pattern search is a family of numerical optimization
methods that do not require the gradient
of the problem to be optimized. Hence PS can be used on functions that are not continuous
or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.
The name, pattern search, was coined by Hooke and Jeeves . An early and simple PS variant is attributed to Fermi
and Metropolis
when they worked at the Los Alamos National Laboratory
as described by Davidon who summarized the algorithm as follows:
that converges to a solution; indeed, pattern search methods can converge to non-stationary points on some relatively tame problems.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
methods that do not require the gradient
Gradient
In vector calculus, the gradient of a scalar field is a vector field that points in the direction of the greatest rate of increase of the scalar field, and whose magnitude is the greatest rate of change....
of the problem to be optimized. Hence PS can be used on functions that are not continuous
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.
The name, pattern search, was coined by Hooke and Jeeves . An early and simple PS variant is attributed to Fermi
Enrico Fermi
Enrico Fermi was an Italian-born, naturalized American physicist particularly known for his work on the development of the first nuclear reactor, Chicago Pile-1, and for his contributions to the development of quantum theory, nuclear and particle physics, and statistical mechanics...
and Metropolis
Nicholas Metropolis
Nicholas Constantine Metropolis was a Greek American physicist.-Work:Metropolis received his B.Sc. and Ph.D. degrees in physics at the University of Chicago...
when they worked at the Los Alamos National Laboratory
Los Alamos National Laboratory
Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...
as described by Davidon who summarized the algorithm as follows:
Convergence
A convergent pattern-search method was proposed by Yu, who proved that it converged using the theory of positive bases. Later, Torczon, Lagarias, and coauthors, used positive-basis techniques to prove the convergence of another pattern search method, on a specific class of functions. Outside of such classes, pattern search is a heuristic that can provide useful approximate solutions for some problem, but can fail on others. Outside of such classes, pattern search is not an iterative methodIterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
that converges to a solution; indeed, pattern search methods can converge to non-stationary points on some relatively tame problems.
See also
- Golden section searchGolden section searchThe golden section search is a technique for finding the extremum of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points...
conceptually resembles PS in its narrowing of the search-range, only for single-dimensional search-spaces. - Nelder–Mead method aka. the simplex method conceptually resembles PS in its narrowing of the search-range for multi-dimensional search-spaces but does so by maintaining n + 1 points for n-dimensional search-spaces where as PS methods only maintain one point in the search-space.
- Luus–JaakolaLuus–JaakolaIn computational engineering, Luus–Jaakola denotes a heuristic for global optimization of a real-valued function. In engineering use, LJ is not an algorithm that terminates with an optimal solution; nor is it an iterative method that generates a sequence of points that converges to an optimal...
samples from a uniform distributionUniform distribution (continuous)In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...
surrounding the current position and uses a simple formula for exponentially decreasing the sampling range. - Random searchRandom searchRandom search is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RS can hence be used on functions that are not continuous or differentiable...
is a related family of optimization methods which sample from a hypersphereHypersphereIn mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...
surrounding the current position. - Random optimizationRandom optimizationRandom optimization is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RO can hence be used on functions that are not continuous or differentiable...
is a related family of optimization methods which sample from a normal distribution surrounding the current position.