Pattern search (optimization) on:
[Wikipedia]
[Google]
[Amazon]
Pattern search (also known as direct search, derivative-free search, or black-box search) is a family of numerical
Positive basis and a class of direct search techniques
€ť. ''Scientia Sinica'' 'Zhongguo Kexue'' 53—68. *Yu, Wen Ci. 1979. â
The convergent property of the simplex evolutionary technique
€ť. ''Scientia Sinica'' 'Zhongguo Kexue'' 69–77. Later, Torczon, Lagarias and co-authors used positive-basis techniques to prove the convergence of another pattern-search method on specific classes of functions. Outside of such classes, pattern search is a
On Search Directions for Minimization Algorithms
” ''Mathematical Programming'' 4: 193—201.* (algorithm summary online).
Pattern search (also known as direct search, derivative-free search, or black-box search) is a family of numerical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
methods that does not require a gradient
In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p is the "direction and rate of fastest increase". If the gr ...
. As a result, it can be used on functions that are not continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous g ...
or differentiable
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
. One such pattern search method is "convergence" (see below), which is based on the theory of positive bases. Optimization attempts to find the best match (the solution that has the lowest error value) in a multidimensional analysis space of possibilities.
History
The name "pattern search" was coined by Hooke and Jeeves. An early and simple variant is attributed toFermi
Enrico Fermi (; 29 September 1901 – 28 November 1954) was an Italian (later naturalized American) physicist and the creator of the world's first nuclear reactor, the Chicago Pile-1. He has been called the "architect of the nuclear age" and t ...
and Metropolis
A metropolis () is a large city or conurbation which is a significant economic, political, and cultural center for a country or region, and an important hub for regional or international connections, commerce, and communications.
A big c ...
when they worked at the Los Alamos National Laboratory
Los Alamos National Laboratory (often shortened as Los Alamos and LANL) is one of the sixteen research and development laboratories of the United States Department of Energy (DOE), located a short distance northwest of Santa Fe, New Mexico, ...
. It is described by Davidon, as follows:
Convergence
Convergence is a pattern search method proposed by Yu, who proved that it converges using the theory of positive bases.*Yu, Wen Ci. 1979. âPositive basis and a class of direct search techniques
€ť. ''Scientia Sinica'' 'Zhongguo Kexue'' 53—68. *Yu, Wen Ci. 1979. â
The convergent property of the simplex evolutionary technique
€ť. ''Scientia Sinica'' 'Zhongguo Kexue'' 69–77. Later, Torczon, Lagarias and co-authors used positive-basis techniques to prove the convergence of another pattern-search method on specific classes of functions. Outside of such classes, pattern search is a
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...
that can provide useful approximate solutions for some issues, but can fail on others. Outside of such classes, pattern search is not an iterative method
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
that converges to a solution; indeed, pattern-search methods can converge to non-stationary points on some relatively tame problems.* Powell, Michael J. D. 1973. âOn Search Directions for Minimization Algorithms
” ''Mathematical Programming'' 4: 193—201.* (algorithm summary online).
See also
*Golden-section search
The golden-section search is a technique for finding an extremum (minimum or maximum) of a function inside a specified interval. For a strictly unimodal function with an extremum inside the interval, it will find that extremum, while for an interv ...
conceptually resembles PS in its narrowing of the search range, only for single-dimensional search spaces.
* Nelder–Mead method
The Nelder–Mead method (also downhill simplex method, amoeba method, or polytope method) is a numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based o ...
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, whereas PS methods computes 2''n'' + 1 points (the central point and 2 points in each dimension).
* Luus–Jaakola In computational engineering, Luus–Jaakola (LJ) 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 generat ...
samples from a uniform distribution
Uniform distribution may refer to:
* Continuous uniform distribution
* Discrete uniform distribution
* Uniform distribution (ecology)
* Equidistributed sequence
See also
*
* Homogeneous distribution
In mathematics, a homogeneous distribution ...
surrounding the current position and uses a simple formula for exponentially decreasing the sampling range.
* Random search Random search (RS) 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. Such optimization methods are also ...
is a related family of optimization methods that sample from a hypersphere
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, call ...
surrounding the current position.
* Random optimization Random optimization (RO) 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. Such optimization methods are als ...
is a related family of optimization methods that sample from a normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu ...
surrounding the current position.
References
{{Major subfields of optimization Optimization algorithms and methods