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

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

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 to Enrico Fermi, Fermi and Nicholas Metropolis, Metropolis when they worked at the Los Alamos National Laboratory. 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, Virginia Torczon, 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#Computer science, heuristic 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 that converges to a solution; indeed, pattern-search methods can converge to non-stationary points on some relatively tame problems.* Michael J. D. Powell, Powell, Michael J. D. 1973. �
On Search Directions for Minimization Algorithms
” ''Mathematical Programming'' 4: 193—201.* (algorithm summary online).

* Golden-section search 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, whereas PS methods computes 2''n'' + 1 points (the central point and 2 points in each dimension). * Luus–Jaakola samples from a Uniform distribution (continuous), uniform distribution surrounding the current position and uses a simple formula for exponentially decreasing the sampling range. * Random search is a related family of optimization methods that sample from a hypersphere surrounding the current position. * Random optimization is a related family of optimization methods that sample from a normal distribution surrounding the current position.

References

{{Major subfields of optimization Optimization algorithms and methods

History

Convergence

See also

References