Ejemplo de convergencia de un método de búsqueda directa en la función de Broyden. En cada iteración, el patrón se mueve al punto que minimiza mejor su función objetivo o se reduce de tamaño si ningún punto es mejor que el actual, hasta que se alcanza la precisión deseada o el algoritmo alcanza un número predeterminado de iteraciones.
La búsqueda de patrones (también conocida como búsqueda directa, búsqueda sin derivadas o búsqueda de caja negra) es una familia de métodos de optimización numérica que no requiere un gradiente . Como resultado, se puede utilizar en funciones que no son continuas o diferenciables . Uno de estos métodos de búsqueda de patrones es la "convergencia" (ver más abajo), que se basa en la teoría de bases positivas. La optimización intenta encontrar la mejor coincidencia (la solución que tiene el valor de error más bajo) en un espacio de análisis multidimensional de posibilidades.
Historia
El nombre de "búsqueda de patrones" fue acuñado por Hooke y Jeeves. [1] Una variante temprana y simple se atribuye a Fermi y Metropolis cuando trabajaban en el Laboratorio Nacional de Los Álamos . Davidon la describe de la siguiente manera :
Variaron un parámetro teórico a la vez en pasos de la misma magnitud, y cuando ningún aumento o disminución en ningún parámetro mejoró aún más el ajuste a los datos experimentales, redujeron a la mitad el tamaño del paso y repitieron el proceso hasta que los pasos se consideraron suficientemente pequeños.
Convergencia
La convergencia es un método de búsqueda de patrones propuesto por Yu, quien demostró que converge utilizando la teoría de bases positivas. [3] Más tarde, Torczon , Lagarias y coautores [4] [5] utilizaron técnicas de base positiva para demostrar la convergencia de otro método de búsqueda de patrones en clases específicas de funciones. Fuera de dichas clases, la búsqueda de patrones es una heurística que puede proporcionar soluciones aproximadas útiles para algunos problemas, pero puede fallar en otros. Fuera de dichas clases, la búsqueda de patrones no es un método iterativo que converge a una solución; de hecho, los métodos de búsqueda de patrones pueden converger a puntos no estacionarios en algunos problemas relativamente sencillos. [6] [7]
Véase también
La búsqueda de sección áurea conceptualmente se asemeja a PS en su estrechamiento del rango de búsqueda, sólo para espacios de búsqueda unidimensionales.
El método Nelder-Mead , también conocido como método simplex, conceptualmente se parece al método PS en su estrechamiento del rango de búsqueda para espacios de búsqueda multidimensionales, pero lo hace manteniendo n + 1 puntos para espacios de búsqueda n -dimensionales, mientras que los métodos PS calculan 2 n + 1 puntos (el punto central y 2 puntos en cada dimensión).
Luus-Jaakola toma muestras de una distribución uniforme que rodea la posición actual y utiliza una fórmula simple para disminuir exponencialmente el rango de muestreo.
La búsqueda aleatoria es una familia relacionada de métodos de optimización que toman muestras de una hiperesfera que rodea la posición actual.
^ Hooke, R.; Jeeves, TA (1961). "Solución de problemas numéricos y estadísticos mediante búsqueda directa". Revista de la ACM . 8 (2): 212–229. doi : 10.1145/321062.321069 . S2CID 10905054.
^ Davidon, WC (1991). "Método de métrica variable para minimización". Revista SIAM sobre optimización . 1 (1): 1–17. CiteSeerX 10.1.1.693.272 . doi :10.1137/0801001. S2CID 1819475.
^ *Yu, Wen Ci. 1979. “Bases positivas y una clase de técnicas de búsqueda directa”. Scientia Sínica [ Zhongguo Kexue ]: 53—68.
Yu, Wen Ci. 1979. “La propiedad convergente de la técnica evolutiva simplex”. Scientia Sínica [ Zhongguo Kexue ]: 69–77.
^ Torczon, VJ (1997). "Sobre la convergencia de algoritmos de búsqueda de patrones" (PDF) . Revista SIAM sobre optimización . 7 (1): 1–25. CiteSeerX 10.1.1.50.3173 . doi :10.1137/S1052623493250780.
^ Dolan, ED; Lewis, RM; Torczon, VJ (2003). "Sobre la convergencia local de la búsqueda de patrones" (PDF) . Revista SIAM sobre optimización . 14 (2): 567–583. CiteSeerX 10.1.1.78.2407 . doi :10.1137/S1052623400374495. hdl :2060/20000109966. S2CID 4226940.
^ * Powell, Michael JD 1973. ”Sobre direcciones de búsqueda para algoritmos de minimización”. Programación matemática 4: 193—201.
^ * McKinnon, KIM (1999). "Convergencia del método simplex de Nelder-Mead a un punto no estacionario". SIAM J. Optim . 9 : 148–158. CiteSeerX 10.1.1.52.3900 . doi :10.1137/S1052623496303482. (Resumen del algoritmo en línea).
