Método Hook-Jeeves

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de octubre de 2018; las comprobaciones requieren 2 ediciones .

El método Hook-Jeeves ( eng. Hooke-Jeeves, búsqueda de patrones ), también conocido como el método de configuración , como el algoritmo Nelder-Mead , se usa para buscar un extremo local incondicional de una función y se refiere a métodos directos, es decir , se basa directamente en los valores de la función. El algoritmo se divide en dos fases: búsqueda exploratoria y búsqueda de patrones.

En la etapa inicial, se establece el punto de partida (lo denotaremos con 1) y los pasos h i a lo largo de las coordenadas. Luego congelamos los valores de todas las coordenadas excepto la 1ra, calculamos los valores de la función en los puntos x 0 + h 0 y x 0 -h 0 (donde x 0 es la primera coordenada del punto, y h 0 es el valor del paso a lo largo de esta coordenada, respectivamente) y vaya al punto con el valor de función más pequeño. En este punto, congelamos los valores de todas las coordenadas excepto la segunda, calculamos los valores de la función en los puntos x 1 +h 1 y x 1 -h 1 , nos movemos al punto con el valor de función más pequeño, etc. para todas las coordenadas. Si para alguna coordenada el valor en el punto de partida es menor que los valores para ambas direcciones del paso, entonces se reduce el paso a lo largo de esta coordenada. Cuando los pasos a lo largo de todas las coordenadas h i se vuelven menores que los valores correspondientes de e i , el algoritmo finaliza y el punto 1 se reconoce como el punto mínimo.

Ilustración de la primera etapa para dos coordenadas:

Así, después de realizar una búsqueda exploratoria sobre todas las coordenadas, obtendremos un nuevo punto con el menor valor de la función en la vecindad (lo denotaremos por 2). Ahora puede pasar a la segunda fase del algoritmo.

En la etapa de búsqueda según la muestra, el punto 3 se traza en la dirección de 1 a 2 a la misma distancia. Sus coordenadas se obtienen mediante la fórmula Si en esta fase, como resultado de la búsqueda exploratoria, fue posible obtener el punto 4, diferente del punto 3, entonces cambiaremos el nombre del punto 2 a 1, y el 4 a 2, y repetiremos la búsqueda por el patrón. Si no es posible encontrar el punto 4 diferente del punto 3, redesignaremos el punto 2 como el punto 1 y repetiremos la primera fase del algoritmo: búsqueda de investigación. ${\overline {x}}_{3}={\overline {x}}_{1}+\lambda ({\overline {x}}_{2}-{\overline {x}}_ {una})$

Ilustración de la segunda etapa para dos coordenadas:

Los nombres de los puntos después del cambio de nombre se marcan entre paréntesis. La ilustración muestra claramente cómo el algoritmo corrige su dirección dependiendo de los valores de función encontrados.

Literatura

R. Hook, T. A. Jeeves "Búsqueda directa de una solución a problemas numéricos y estáticos", 212-219 págs., 1961.
CT Kelly. Métodos iterativos para optimización, 180 p

Enlaces

https://web.archive.org/web/20120905151449/http://www.theweman.info/topics/t4r5part1.html
Métodos de optimización multidimensional en Intuit.ru .
AV. Attetkov, S.V. Galkin, V. S. Zarubín. Método Hook-Jeeves // Métodos de optimización . - M. : Editorial de MSTU im. NORDESTE. Bauman, 2003. - S. 285. - 440 p. - (Matemáticas en la Universidad Técnica; Edición XIV). (enlace no disponible)

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial