derecha|miniaturadeimagen|300x300px| Ejemplo de convergencia de un método de búsqueda directa sobre 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 punto actual, hasta que se logra la precisión deseada o el algoritmo alcanza un número predeterminado de iteraciones. La búsqueda de patrones (conocida también como búsqueda directa, búsqueda sin derivados 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 usar en funciones que no son continuas o diferenciables. Uno de estos métodos de búsqueda de patrones es la «convergencia», que se basa en la teoría de las 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 posibilidades del análisis multidimensional.
Historia El nombre de «búsqueda de patrones» fue acuñado por Hooke y Jeeves. Una variante temprana y sencilla se atribuye a Fermi y Metropolis cuando trabajaban en el Laboratorio Nacional de Los Álamos. Es descrito por Davidon, de la siguiente manera:
Convergencia La convergencia es un método de búsqueda de patrones propuesto por Yu, quien demostró que converge utilizando la teoría de las bases positivas.Yu, Wen Ci. 1979. “Positive basis and a class of direct search techniques”. Scientia Sinica [Zhongguo Kexue]: 53—68. Más tarde, Torczon, Lagarias et al. utilizaron técnicas de base positiva para demostrar la convergencia de otro método de búsqueda de patrones en clases de funciones específicas. Fuera de tales clases, la búsqueda de patrones es una heurística que puede proporcionar soluciones aproximadas útiles para algunos problemas, pero puede fallar en otros. La búsqueda de patrones no es un método iterativo que converge en una solución; de hecho, los métodos de búsqueda de patrones pueden converger en puntos no estacionarios en algunos problemas relativamente sencillos.<ref name="McKnnon99">"Convergence of the Nelder–Mead simplex method to a non-stationary point". SIAM J. Optim. 9: 148–158. CiteSeerX <span class="cs1-lock-free" title="Freely accessible">10.1.1.52.3900. doi:10.1137/S1052623496303482. (algorithm summary online).</span></ref>
Véase también
Búsqueda de sección áurea conceptualmente se asemeja a la búsqueda de patrones en la reducción del rango de búsqueda, solo para espacios unidimensionales. Método Nelder-Mead también conocido como método símplex se parece conceptualmente a la búsqueda de patrones en la reducción del rango de búsqueda para espacios de búsqueda multidimensionales, pero lo hace manteniendo n + 1 puntos para espacios n-dimensionales, mientras que los métodos de búsqueda de patrones calculan 2n + 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 usa una fórmula simple para disminuir exponencialmente el rango de muestreo. Búsqueda aleatoria es una familia de métodos de optimización que toman muestras de una hiperesfera que rodea la posición actual. Optimización aleatoria es una familia de métodos de optimización que muestrean una distribución normal que rodea la posición actual.
Referencias
Enlaces externos
Categoría:Optimización