Pattern search (optimization)
Family of numerical optimization methods
title: "Pattern search (optimization)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["optimization-algorithms-and-methods"] description: "Family of numerical optimization methods" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/Pattern_search_(optimization)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Family of numerical optimization methods ::
::figure[src="https://upload.wikimedia.org/wikipedia/commons/1/14/Direct_search_BROYDEN.gif" caption="Example of convergence of a direct search method on the [[Broyden function]]. At each iteration, the pattern either moves to the point which best minimizes its objective function, or shrinks in size if no point is better than the current point, until the desired accuracy has been achieved, or the algorithm reaches a predetermined number of iterations."] ::
Pattern search (also known as direct search, derivative-free search, or black-box search) is a family of numerical optimization methods that does not require a gradient. As a result, it can be used on functions that are not continuous or differentiable. 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 Fermi and Metropolis when they worked at the Los Alamos National Laboratory. It is described by Davidon, as follows: ::quote 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 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
References
|last1=Hooke |first1=R. |last2=Jeeves |first2=T.A. |title="Direct search" solution of numerical and statistical problems |journal=Journal of the ACM |year=1961 |volume=8 |number=2 |pages=212–229 |doi=10.1145/321062.321069 |s2cid=10905054 |doi-access=free
|last=Davidon |first=W.C. |title=Variable metric method for minimization |journal=SIAM Journal on Optimization |year=1991 |volume=1 |number=1 |pages=1–17 |doi=10.1137/0801001 |citeseerx=10.1.1.693.272 |s2cid=1819475
|last=Torczon |first=V.J.|authorlink= Virginia Torczon |title=On the convergence of pattern search algorithms |journal=SIAM Journal on Optimization |year=1997 |volume=7 |number=1 |pages=1–25 |doi=10.1137/S1052623493250780 |url=http://www.cs.wm.edu/~va/research/unc.pdf |citeseerx=10.1.1.50.3173
|last1=Dolan |first1=E.D. |last2=Lewis |first2=R.M. |last3=Torczon |first3=V.J. |title=On the local convergence of pattern search |journal=SIAM Journal on Optimization |year=2003 |volume=14 |number=2 |pages=567–583 |doi=10.1137/S1052623400374495 |hdl=2060/20000109966 |url=http://www.cs.wm.edu/~va/research/local.pdf |citeseerx=10.1.1.78.2407 |s2cid=4226940
References
- Powell, Michael J. D.]] 1973. ”[https://link.springer.com/article/10.1007/BF01584660 On Search Directions for Minimization Algorithms].” ''Mathematical Programming'' 4: 193—201.
- McKinnon, K. I. M.. (1999). "Convergence of the Nelder–Mead simplex method to a non-stationary point". SIAM J. Optim..
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::