Método Nelder-Mead

Nelder Mead1.gif
Nelder Mead2.gif

Búsqueda del valor mínimo a través del simplex Nelder–Mead en las función banana de Rosenbrock (arriba) y en la función de Himmelblau (abajo)

El método Nelder-Mead es un algoritmo de optimización ampliamente utilizado. Es debido a Nelder y Mead (1965) y es un método numérico para minimizar una función objetiva en un espacio multidimensional.

El método utiliza el concepto de un simplex, que es un politopo de N+1 vértices en N dimensiones: un segmento de línea en una línea, un triángulo en un plano, un tetraedro en un espacio tridimensional y así sucesivamente.

El método busca de modo aproximado una solución óptima local a un problema con N variables cuando la función a minimizar varía suavemente.

Ejemplo de utilización

Por ejemplo, un ingeniero que diseñe un puente colgante ha de elegir el grosor de los cables laterales, los cables más largos y del soporte que irá asfaltado. Estos elementos están ligados para un correcto diseño del puente y no es fácil imaginar el efecto en el cambio de cada uno de los espesores. El ingeniero puede usar el método Nelder-Mead para generar diseños de prueba, fijando los grosores de los elementos, que son probados en un modelo de ordenador que tiene en cuenta otros parámetros (vibraciones, vientos, materiales de construcción…).

Así se introduce una función, llamémosla inestabilidad del puente que depende de los grosores de los elementos con los que se construye, que interesa hacer mínima ante otros factores externos (vibraciones, vientos…). Como cada vez que se ejecuta este modelo que tiene en cuenta los factores externos se consume mucho tiempo de cálculo es importante variar los grosores con idea para no malgastar recursos.

El método Nelder-Mead genera una nueva posición de prueba (valor de los grosores extrapolando el comportamiento de la función en los vértices de un simplex. Así no es necesario calcular probar todos los valores posibles de la función (todos los grosores) sino que el algoritmo va reemplazando cada vez uno de los puntos de prueba ajustando con idea para encontrar la solución que minimiza la función más rápidamente.

El modo más sencillo de hacerlo es reemplazar el peor punto con un punto reflejado en el resto de N-1 puntos considerados como un plano (de ahí la extrapolación). Si este punto da mejor resultado, el algoritmo prueba a estirarse tomando los valores exponencialmente en una línea que contenga este punto. Por otra parte, si este nuevo punto no es mucho mejor que el valor previo, entonces estamos en un valle (buscamos un mínimo, como un gran hoyo) y el algoritmo encoge el simplex hacia el mejor punto.

Other Languages