Búsqueda de patrones (optimización)

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 gradiente . Por lo tanto, puede aplicarse a funciones que no son continuas ni diferenciables . Un ejemplo de este método es la "convergencia" (véase más adelante), que se basa en la teoría de bases positivas. La optimización busca encontrar la mejor coincidencia (la solución con el menor error) en un espacio de análisis multidimensional de posibilidades.

El término "búsqueda de patrones" fue acuñado por Hooke y Jeeves. ^{[ 1 ]} Una variante temprana y sencilla se atribuye a Fermi y Metropolis cuando trabajaban en el Laboratorio Nacional de Los Alamos . Davidon la describe, ^{[ 2 ]} de la siguiente manera:

Variaron un parámetro teórico a la vez mediante incrementos de la misma magnitud, y cuando ningún aumento o disminución de dicho parámetro mejoraba aún más el ajuste a los datos experimentales, redujeron a la mitad el tamaño del incremento y repitieron el proceso hasta que consideraron que los incrementos eran suficientemente pequeños.

La convergencia es un método de búsqueda de patrones propuesto por Yu, quien demostró su convergencia utilizando la teoría de bases positivas. ^{[ 3 ]} Posteriormente, Torczon , Lagarias y coautores ^{[ 4 ] [ 5 ]} utilizaron técnicas de bases positivas 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 ]}

• La búsqueda por sección áurea se asemeja conceptualmente a la búsqueda por secciones en su reducción del rango de búsqueda, solo que para espacios de búsqueda unidimensionales.
• El método de Nelder-Mead, también conocido como método simplex, se asemeja conceptualmente al método PS en su reducción 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).
• El método Luus-Jaakola toma muestras de una distribución uniforme que rodea la posición actual y utiliza una fórmula sencilla 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.
• La optimización aleatoria es una familia relacionada de métodos de optimización que toman muestras de una distribución normal que rodea la posición actual.