Pattern search (optimization)

For other uses, see Pattern search.

Example of convergence of a direct search method on Broyden function

Pattern search (also known as direct search, derivative-free search, or black-box search) is a family of numerical optimization methods that do not require a gradient of the problem. As a result, it can be used on functions that are not continuous or differentiable.

The name "pattern search" was coined by Hooke and Jeeves. An early and simple variant is attributed to Fermi and Metropolis when they worked at the Los Alamos National Laboratory described by Davidon, as follows:

They varied one theoretical parameter at a time by steps of the same magnitude, and when no such increase or decrease in any one parameter further improved the fit to the experimental data, they halved the step size and repeated the process until the steps were deemed sufficiently small.

Convergence

Convergence .</ref> hyfhyi

See also

• 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 2n + 1 points (the central point and 2 points in each dimension).
• Luus–Jaakola samples from a 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.