Método Simplex de Nelder y Mead
| ||||
Método Simplex de Nelder y Mead. Constituye un algoritmo de optimización ampliamente utilizado. Es debido a Nelder y Mead (Nelder and Mead 1965) y es un método para minimizar una función objetivo 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
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 un 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.
Como otros algoritmos de optimización, Nelder-Mead a veces se queda bloqueado en un mínimo local (una zona que es un mínimo de la función comparado con los puntos de alrededor pero hay motivos para pensar que existe un mímino mejor en otra parte). El algoritmo se da cuenta y se reinicia con un nuevo simplex que empiece en el mejor valor encontrado. Esto puede extenderse de la misma manera que en el simulated annealing para tratar de escapar de los mínimos locales.
Existen muchas variaciones dependiendo de la naturaleza del problema que se quiera resolver. La más usual es, quizá, usar un simplex pequeño de tamaño constante que salte de gradientes locales a máximos locales. Imagine un pequeño triángulo en un mapa 3D de una cadena montañosa, subiendo a una de las montañas buscando el pico, buscando como objetivo final encontrar el pico más alto de la cordillera. Esta variación suele funcionar peor que el método original de Nelder-Mead descrito en el artículo pues requiere muchos pequeños pasos intermedios (subir a todas las montañas para ver cuál es la más alta).
Ventajas y Desventajas del método
Como ventajas podemos mencionar que es un método heurístico. Se basa en consideraciones geométricas y no requiere el uso de derivadas de la función objetivo. Es de gran eficacia incluso para ajustar gran número de parámetros. Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente. Es fácil de implementar y usar, y sin embargo tiene una alta eficacia. Por otra parte se dice que converge más lentamente que otros métodos pues requiere mayor número de iteraciones.
Fuentes
- Nelder, J. and R. Mead (1965). "A simplex method for functions minimizations." Computer Journal 77(4): 308–313.
