Pattern search (optimization)

<h2 id="history">History</h2>
The name "pattern search" was coined by Hooke and Jeeves.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> An early and simple variant is attributed to <a href="/facts/Enrico_Fermi/cmYcY15H">Fermi</a> and <a href="/facts/Nicholas_Metropolis/f2XPGUKk">Metropolis</a> when they worked at the <a href="/facts/Los_Alamos_National_Laboratory/tlrLkV7r">Los Alamos National Laboratory</a>. It is described by Davidon,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> as follows:

<blockquote>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.</blockquote>
<h2 id="convergence">Convergence</h2>
Convergence is a pattern search method proposed by Yu, who proved that it converges using the theory of positive bases.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> Later, <a href="/facts/Virginia_Torczon/629923Iq">Torczon</a>, Lagarias and co-authors<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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 <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic</a> that can provide useful approximate solutions for some issues, but can fail on others. Outside of such classes, pattern search is not an <a href="/facts/Iterative_method/uKMAJhEh">iterative method</a> that converges to a solution; indeed, pattern-search methods can converge to non-stationary points on some relatively tame problems.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Golden-section_search/vvXlfXeJ">Golden-section search</a> conceptually resembles PS in its narrowing of the search range, only for single-dimensional search spaces.</li>
<li><a href="/facts/Nelder%25E2%2580%2593Mead_method/6aXswEax">Nelder–Mead method</a> 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).</li>
<li><a href="/facts/Luus%25E2%2580%2593Jaakola/uAXx1Gmk">Luus–Jaakola</a> samples from a <a href="/facts/Uniform_distribution_(continuous)/XbnlVljT">uniform distribution</a> surrounding the current position and uses a simple formula for exponentially decreasing the sampling range.</li>
<li><a href="/facts/Random_search/b4hcrusx">Random search</a> is a related family of optimization methods that sample from a <a href="/facts/Hypersphere/bFu2S7E2">hypersphere</a> surrounding the current position.</li>
<li><a href="/facts/Random_optimization/VP7B9RfI">Random optimization</a> is a related family of optimization methods that sample from a <a href="/facts/Normal_distribution/UapjjPyQ">normal distribution</a> surrounding the current position.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hooke, R.; Jeeves, T.A. (1961). ""Direct search" solution of numerical and statistical problems". Journal of the ACM. 8 (2): 212–229. doi:10.1145/321062.321069. S2CID 10905054. <a href="https://doi.org/10.1145%2F321062.321069" target="_blank">https://doi.org/10.1145%2F321062.321069</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Davidon, W.C. (1991). "Variable metric method for minimization". SIAM Journal on Optimization. 1 (1): 1–17. CiteSeerX 10.1.1.693.272. doi:10.1137/0801001. S2CID 1819475. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">*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.
 <a href="http://engine.scichina.com/doi/10.1360/za1979-9-S1-53" target="_blank">http://engine.scichina.com/doi/10.1360/za1979-9-S1-53</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Torczon, V.J. (1997). "On the convergence of pattern search algorithms" (PDF). SIAM Journal on Optimization. 7 (1): 1–25. CiteSeerX 10.1.1.50.3173. doi:10.1137/S1052623493250780. <a href="/wiki/Virginia_Torczon" target="_blank">/wiki/Virginia_Torczon</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Dolan, E.D.; Lewis, R.M.; Torczon, V.J. (2003). "On the local convergence of pattern search" (PDF). SIAM Journal on Optimization. 14 (2): 567–583. CiteSeerX 10.1.1.78.2407. doi:10.1137/S1052623400374495. hdl:2060/20000109966. S2CID 4226940. <a href="http://www.cs.wm.edu/~va/research/local.pdf" target="_blank">http://www.cs.wm.edu/~va/research/local.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">* Powell, Michael J. D. 1973. ”On Search Directions for Minimization Algorithms.” Mathematical Programming 4: 193—201. <a href="/wiki/Michael_J._D._Powell" target="_blank">/wiki/Michael_J._D._Powell</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">* McKinnon, K. I. M. (1999). "Convergence of the Nelder–Mead simplex method to a non-stationary point". SIAM J. Optim. 9: 148–158. CiteSeerX 10.1.1.52.3900. doi:10.1137/S1052623496303482. (algorithm summary online). <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Pattern search (optimization) open-in-new

Pattern search (optimization)