miniatura|300x300px| Exemple de convergència d'un mètode de cerca directa sobre la funció de Broyden. En cada iteració, el patró es mou al punt que minimitza més la seva funció objectiu o es redueix la mida si cap punt és millor que el punt actual, fins que s'aconsegueix la precisió desitjada o l'algorisme arriba a un nombre determinat d'iteracions. La cerca de patrons (també coneguda com cerca directa, cerca sense derivades o cerca de caixa negra) és una família de mètodes doptimització numèrica que no requereix conèixer el gradient de la funció objectiu. Per tant, es pot utilitzar en funcions que no són contínues o diferenciables. Un d'aquests mètodes de cerca de patrons és la «convergència», que es basa en la teoria de les bases positives. L'optimització intenta trobar la millor coincidència (la solució que té el valor d'error més baix) en un espai de spossibilitats de l'anàlisi multidimensional.
Història El nom de «cerca de patrons» va ser encunyat per Hooke i Jeeves. Una primera variant més senzilla és atribuïda a Fermi i Metropolis quan treballaven al Laboratori Nacional Los Alamos. Davidon va desciure aquest primer procediment com:
Convergència La convergència és un mètode de la família d'algorismes de cerca de patrons. Va ser proposat per Yu, que va demostrar que convergeix utilitzant la teoria de bases positives.*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. Més tard, Virginia Torczon, Lagarias i coautors van utilitzar tècniques de bases positives per demostrar la convergència d'un altre mètodes de cerca de patrons aplicat a classes específiques de funcions. Fora d'aquestes classes, la cerca de patrons és un algorisme heurístic que pot proporcionar solucions aproximades útils en alguns casos, però que pot no funcionar en d'altres. Fora d'aquestes classes, la cerca de patrons no és un mètode iteratiu que convergeixi a una solució; en efecte, els mètodes de cerca de patrons poden convergir a punts no esttacionaris en problemes relativament senzills.* Powell, Michael J. D. 1973. ”On Search Directions for Minimization Algorithms.” Mathematical Programming 4: 193—201.* (algorithm summary online).
Vegeu també Mètode Nelder-Mead
Referències
Categoria:Optimització