Método de Nelder-Mead

El método de Nelder-Mead (también conocido como método simplex descendente , método ameba o método politopo ) es un método numérico que se utiliza para encontrar un mínimo o máximo local de una función objetivo en un espacio multidimensional. Es un método de búsqueda directa (basado en la comparación de funciones) y se aplica frecuentemente a problemas de optimización no lineal cuyas derivadas pueden ser desconocidas. Sin embargo, la técnica de Nelder-Mead es un método de búsqueda heurística que puede converger a puntos no estacionarios ^{[ 1 ]} en problemas que pueden resolverse mediante métodos alternativos. ^{[ 2 ]}

La técnica de Nelder-Mead fue propuesta por John Nelder y Roger Mead en 1965, ^{[ 3 ]} como un desarrollo del método de Spendley et al. ^{[ 4 ]}

El método utiliza el concepto de símplice , que es un politopo especial de n  +  1 vértices en n dimensiones. Ejemplos de símplices incluyen un segmento de línea en el espacio unidimensional, un triángulo en el espacio bidimensional, un tetraedro en el espacio tridimensional, etc.

El método aproxima un óptimo local de un problema con n variables cuando la función objetivo varía suavemente y es unimodal . Las implementaciones típicas minimizan funciones, y nosotros maximizamos.${\displaystyle f(\mathbf {x} )}$minimizando${\displaystyle -f(\mathbf {x} )}$.

Por ejemplo, un ingeniero de puentes colgantes debe elegir el grosor de cada puntal, cable y pilar. Estos elementos son interdependientes, pero no es fácil visualizar el impacto de modificar alguno en particular. La simulación de estructuras tan complejas suele ser extremadamente costosa desde el punto de vista computacional, pudiendo tardar varias horas por ejecución. El método de Nelder-Mead, en su versión original, requiere no más de dos evaluaciones por iteración, salvo la operación de reducción descrita posteriormente, lo que resulta atractivo en comparación con otros métodos de optimización de búsqueda directa. Sin embargo, el número total de iteraciones para alcanzar el óptimo propuesto puede ser elevado.

El método de Nelder-Mead en n dimensiones mantiene un conjunto de n  +  1 puntos de prueba dispuestos como un simplex . Luego, extrapola el comportamiento de la función objetivo medida en cada punto de prueba para encontrar un nuevo punto y reemplazar uno de los puntos de prueba antiguos con el nuevo, y así progresa la técnica. El enfoque más simple es reemplazar el peor punto con un punto reflejado a través del centroide de los n puntos restantes. Si este punto es mejor que el mejor punto actual, podemos intentar extender exponencialmente a lo largo de esta línea. Por otro lado, si este nuevo punto no es mucho mejor que el valor anterior, entonces estamos cruzando un valle, por lo que reducimos el simplex hacia un punto mejor. Una explicación intuitiva del algoritmo de "Numerical Recipes": ^{[ 5 ]}

El método del simplex descendente ahora toma una serie de pasos, la mayoría de los cuales simplemente mueven el punto del simplex donde la función es máxima ("punto más alto") a través de la cara opuesta del simplex hasta un punto más bajo. Estos pasos se llaman reflexiones y están construidos para conservar el volumen del simplex (y, por lo tanto, mantener su no degeneración). Cuando es posible, el método expande el simplex en una u otra dirección para dar pasos más grandes. Cuando llega a un "fondo de valle", el método se contrae en la dirección transversal e intenta deslizarse por el valle. Si se da la situación de que el simplex intenta "pasar por el ojo de una aguja", se contrae en todas direcciones, apretándose alrededor de su punto más bajo (mejor).

A diferencia de los métodos de optimización modernos, la heurística de Nelder-Mead puede converger a un punto no estacionario, a menos que el problema satisfaga condiciones más estrictas que las necesarias para los métodos modernos. ^{[ 1 ]} Se conocen mejoras modernas sobre la heurística de Nelder-Mead desde 1979. ^{[ 2 ]}

Existen muchas variantes según la naturaleza del problema que se esté resolviendo. Una variante común utiliza un simplex pequeño de tamaño constante que sigue aproximadamente la dirección del gradiente (lo que produce el descenso más pronunciado ). Imagínese un pequeño triángulo en un mapa de elevación que se desplaza por un valle hasta un punto más bajo. Este método también se conoce como el método del poliedro flexible . Sin embargo, suele tener un rendimiento inferior al del método descrito en este artículo, ya que realiza pasos pequeños e innecesarios en áreas de poco interés.

(Esto se aproxima al procedimiento descrito en el artículo original de Nelder-Mead).

Estamos tratando de minimizar la función${\displaystyle f(\mathbf {x} )}$, dónde${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$Nuestros puntos de prueba actuales son${\displaystyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{n+1}}$.

Nota :${\displaystyle \alpha }$,${\displaystyle \gamma }$,${\displaystyle \rho }$y${\displaystyle \sigma }$son respectivamente los coeficientes de reflexión, expansión, contracción y reducción. Los valores estándar son${\displaystyle \alpha =1}$,${\displaystyle \gamma =2}$,${\displaystyle \rho =1/2}$y${\displaystyle \sigma =1/2}$.

Para la reflexión , ya que${\displaystyle \mathbf {x} _{n+1}}$es el vértice con el valor asociado más alto entre los vértices, podemos esperar encontrar un valor más bajo en la reflexión de${\displaystyle \mathbf {x} _{n+1}}$en la cara opuesta formada por todos los vértices${\displaystyle \mathbf {x} _{i}}$excepto${\displaystyle \mathbf {x} _{n+1}}$.

Para la expansión , si el punto de reflexión${\displaystyle \mathbf {x} _{r}}$es el nuevo mínimo a lo largo de los vértices, podemos esperar encontrar valores interesantes a lo largo de la dirección desde${\displaystyle \mathbf {x} _{o}}$a${\displaystyle \mathbf {x} _{r}}$.

En cuanto a la contracción , si${\displaystyle f(\mathbf {x} _{r})>f(\mathbf {x} _{n})}$, podemos esperar que un mejor valor estará dentro del simplex formado por todos los vértices${\displaystyle \mathbf {x} _{i}}$.

Finalmente, el psiquiatra maneja el caso raro de que la contracción alejándose del punto más grande aumenta${\displaystyle f}$, algo que no puede ocurrir suficientemente cerca de un mínimo no singular. En ese caso, contraemos hacia el punto más bajo con la esperanza de encontrar un paisaje más simple. Sin embargo, Nash señala que la aritmética de precisión finita a veces puede no reducir realmente el simplex, e implementó una verificación de que el tamaño se reduce efectivamente. ^{[ 6 ]}

El simplex inicial es importante. De hecho, un simplex inicial demasiado pequeño puede conducir a una búsqueda local, por lo que el NM puede atascarse más fácilmente. Por lo tanto, este simplex debe depender de la naturaleza del problema. Sin embargo, el artículo original sugirió un simplex donde se da un punto inicial como${\displaystyle \mathbf {x} _{1}}$, mientras que los demás se generan con un paso fijo a lo largo de cada dimensión por turno. Por lo tanto, el método es sensible al escalado de las variables que componen${\displaystyle \mathbf {x} }$.

Se necesitan criterios para romper el ciclo iterativo. Nelder y Mead utilizaron la desviación estándar muestral de los valores de la función del simplex actual. Si estos caen por debajo de cierta tolerancia, el ciclo se detiene y se devuelve el punto más bajo del simplex como óptimo propuesto. Nótese que una función muy "plana" puede tener valores de función casi iguales en un dominio amplio, por lo que la solución será sensible a la tolerancia. Nash añade la prueba de contracción como otro criterio de terminación. ^{[ 6 ]} Nótese que los programas terminan, mientras que las iteraciones pueden converger.

• Avriel, Mordecai (2003). Programación no lineal: análisis y métodos . Dover Publishing. ISBN 978-0-486-43227-4.
• Coope, ID; Price, CJ (2002). "Bases positivas en optimización numérica". Optimización computacional y aplicaciones . 21 (2): 169– 176. doi : 10.1023/A:1013760716801 . S2CID 15947440 . 
• Gill, Philip E.; Murray, Walter; Wright, Margaret H. (1981). «Métodos para funciones no suaves multivariadas». Optimización práctica . Nueva York: Academic Press. págs. 93-96 . ISBN  978-0-12-283950-4.
• Kowalik, J.; Osborne, MR (1968). Métodos para problemas de optimización sin restricciones . Nueva York: Elsevier. págs. 24–27 . ISBN  0-444-00041-0.
• Swann, WH (1972). «Métodos de búsqueda directa». En Murray, W. (ed.). Métodos numéricos para la optimización sin restricciones . Nueva York: Academic Press. pp. 13–28 . ISBN  978-0-12-512250-4.

• Explicación y visualización del algoritmo Nelder-Mead (Simplex descendente) con la función banana de Rosenbrock.
• John Burkardt: Código Nelder-Mead en Matlab : tenga en cuenta que una variación del método Nelder-Mead también está implementada por la función fminsearch de Matlab.
• Optimización de Nelder-Mead en Python con la biblioteca SciPy.
• nelder-mead - Una implementación en Python del método de Nelder-Mead
• NelderMead() - Una implementación en Go/Golang
• SOVA 1.0 (software gratuito) Archivado el 6 de junio de 2013 en Wayback Machine - Optimización simplex para diversas aplicaciones
• - HillStormer, una herramienta práctica para la optimización simplex con restricciones lineales, multivariables y no lineales, desarrollada por Nelder Mead.