Método Nelder-Mead

Algoritmo de optimización numérica

Una iteración del método Nelder-Mead sobre el espacio bidimensional.

Búsqueda sobre la función banana de Rosenbrock

Búsqueda sobre la función de Himmelblau

Búsqueda mínima de Nelder-Mead de la función de Simionescu . Los vértices símplex se ordenan por su valor, siendo 1 el valor más bajo (mejor).

El método de Nelder-Mead (también método simplex descendente , método de la ameba o método del politopo ) es un método numérico utilizado para encontrar el mínimo o máximo 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 a menudo a problemas de optimización no lineal para los que las derivadas pueden no conocerse. 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 Nelder-Mead fue propuesta por John Nelder y Roger Mead en 1965, ^[3] como un desarrollo del método de Spendley et al. ^[4]

Descripción general

El método utiliza el concepto de símplex , que es un politopo especial de n  + 1 vértices en n dimensiones. Algunos ejemplos de símplex son 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 las funciones y maximizamos minimizando . ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle -f(\mathbf {x} )}$

Por ejemplo, un ingeniero de puentes colgantes tiene que elegir el grosor de cada puntal, cable y pilar. Estos elementos son interdependientes, pero no es fácil visualizar el impacto de cambiar cualquier elemento específico. La simulación de estructuras tan complicadas suele ser extremadamente costosa en términos computacionales, y puede llevar más de horas por ejecución. El método Nelder-Mead requiere, en la variante original, no más de dos evaluaciones por iteración, excepto por la operación de reducción que se describe más adelante, que es atractiva 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 alto.

Nelder–Mead en n dimensiones mantiene un conjunto de n  + 1 puntos de prueba dispuestos como un símplex . Luego extrapola el comportamiento de la función objetivo medida en cada punto de prueba para encontrar un nuevo punto de prueba y reemplazar uno de los puntos de prueba antiguos por el nuevo, y así la técnica avanza. El enfoque más simple es reemplazar el peor punto por un punto reflejado a través del centroide de los n puntos restantes . Si este punto es mejor que el mejor punto actual, entonces podemos intentar extenderlo 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 encogemos el símplex hacia un punto mejor. Una explicación intuitiva del algoritmo de "Recetas numéricas": ^[5]

El método del símplex descendente ahora requiere una serie de pasos, la mayoría de los cuales simplemente mueven el punto del símplex donde la función es más grande (“punto más alto”) a través de la cara opuesta del símplex hasta un punto más bajo. Estos pasos se llaman reflexiones y están construidos para conservar el volumen del símplex (y, por lo tanto, mantener su no degeneración). Cuando puede hacerlo, el método expande el símplex 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 filtrarse por el valle. Si hay una situación en la que el símplex está tratando de “pasar por el ojo de una aguja”, se contrae en todas las direcciones, tirando de sí mismo 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 de la heurística de Nelder-Mead desde 1979. ^[2]

Existen muchas variaciones según la naturaleza real del problema que se está resolviendo. Una variante común utiliza un símplex pequeño de tamaño constante que sigue aproximadamente la dirección del gradiente (lo que da como resultado el descenso más pronunciado ). Visualice un triángulo pequeño en un mapa de elevación que se mueve de un lado a otro en un valle hasta un fondo local. Este método también se conoce como el método del poliedro flexible . Sin embargo, este método tiende a tener un rendimiento deficiente en comparación con el método descrito en este artículo porque realiza pasos pequeños e innecesarios en áreas de poco interés.

Una posible variación del algoritmo NM

(Esto se aproxima al procedimiento del artículo original de Nelder–Mead).

Método de Nelder-Mead aplicado a la función de Rosenbrock

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

1. Ordenar según los valores en los vértices:

   ${\displaystyle f(\mathbf {x} _{1})\leq f(\mathbf {x} _{2})\leq \cdots \leq f(\mathbf {x} _{n+1}).}$

   Comprueba si el método debe detenerse. Consulta Terminación (a veces denominada "convergencia").

2. Calcular , el centroide de todos los puntos excepto . ${\displaystyle \mathbf {x} _{o}}$ ${\displaystyle \mathbf {x} _{n+1}}$
3. Reflexión
   Calcular el punto reflejado con . ${\displaystyle \mathbf {x} _{r}=\mathbf {x} _{o}+\alpha (\mathbf {x} _{o}-\mathbf {x} _{n+1})}$ ${\displaystyle \alpha >0}$
   Si el punto reflejado es mejor que el segundo peor, pero no mejor que el mejor, es decir , ${\displaystyle f(\mathbf {x} _{1})\leq f(\mathbf {x} _{r})<f(\mathbf {x} _{n})}$

   luego obtenga un nuevo simplex reemplazando el peor punto con el punto reflejado y vaya al paso 1. ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{r}}$

4. Expansión
   Si el punto reflejado es el mejor punto hasta el momento, , ${\displaystyle f(\mathbf {x} _{r})<f(\mathbf {x} _{1})}$

   Luego calcula el punto expandido con . ${\displaystyle \mathbf {x} _{e}=\mathbf {x} _{o}+\gamma (\mathbf {x} _{r}-\mathbf {x} _{o})}$ ${\displaystyle \gamma >1}$

   Si el punto expandido es mejor que el punto reflejado, , ${\displaystyle f(\mathbf {x} _{e})<f(\mathbf {x} _{r})}$

   luego obtenga un nuevo simplex reemplazando el peor punto con el punto expandido y vaya al paso 1; ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{e}}$

   de lo contrario, obtenga un nuevo símplex reemplazando el peor punto con el punto reflejado y vaya al paso 1. ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{r}}$

5. Contracción
   Aquí es seguro que . (Tenga en cuenta que es el segundo o "próximo" al peor punto). ${\displaystyle f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n})}$ ${\displaystyle \mathbf {x} _{n}}$
   Si , ${\displaystyle f(\mathbf {x} _{r})<f(\mathbf {x} _{n+1})}$

   Luego calcula el punto contraído en el exterior con . ${\displaystyle \mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{r}-\mathbf {x} _{o})}$ ${\displaystyle 0<\rho \leq 0.5}$

   Si el punto contraído es mejor que el punto reflejado, es decir , ${\displaystyle f(\mathbf {x} _{c})<f(\mathbf {x} _{r})}$

   luego obtenga un nuevo simplex reemplazando el peor punto con el punto contraído y vaya al paso 1; ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{c}}$

   De lo contrario, vaya al paso 6;

   Si , ${\displaystyle f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n+1})}$

   Luego calcula el punto contraído en el interior con . ${\displaystyle \mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{n+1}-\mathbf {x} _{o})}$ ${\displaystyle 0<\rho \leq 0.5}$

   Si el punto contraído es mejor que el peor punto, es decir , ${\displaystyle f(\mathbf {x} _{c})<f(\mathbf {x} _{n+1})}$

   luego obtenga un nuevo simplex reemplazando el peor punto con el punto contraído y vaya al paso 1; ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{c}}$

   De lo contrario, vaya al paso 6;

6. Encoger
   Reemplace todos los puntos excepto el mejor ( ) con ${\displaystyle \mathbf {x} _{1}}$
   ${\displaystyle \mathbf {x} _{i}=\mathbf {x} _{1}+\sigma (\mathbf {x} _{i}-\mathbf {x} _{1})}$y vaya al paso 1.

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

Para la reflexión , dado que 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 en la cara opuesta formada por todos los vértices excepto . ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{n+1}}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle \mathbf {x} _{n+1}}$

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

Respecto a la contracción , si , podemos esperar que un mejor valor esté dentro del símplex formado por todos los vértices . ${\displaystyle f(\mathbf {x} _{r})>f(\mathbf {x} _{n})}$ ${\displaystyle \mathbf {x} _{i}}$

Por último, la contracción se ocupa del caso poco frecuente de que la contracción a partir del punto más grande aumente , algo que no puede ocurrir lo suficientemente cerca de un mínimo no singular. En ese caso, nos contraemos hacia el punto más bajo con la expectativa de encontrar un paisaje más simple. Sin embargo, Nash señala que la aritmética de precisión finita a veces puede fallar en la contracción del símplex, e implementó una verificación de que el tamaño se reduce realmente. ^[6] ${\displaystyle f}$

Simplex inicial

El símplex inicial es importante. De hecho, un símplex inicial demasiado pequeño puede llevar a una búsqueda local, por lo que el modelo numérico puede atascarse más fácilmente. Por lo tanto, este símplex debería depender de la naturaleza del problema. Sin embargo, el artículo original sugería un símplex en el que se da un punto inicial como , y 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 escalamiento de las variables que componen . ${\displaystyle \mathbf {x} _{1}}$ ${\displaystyle \mathbf {x} }$

Terminación

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

Véase también

• Optimización sin derivadas
• CÓBILA
• NUEVA UOA
• Lincoa
• Método de gradiente conjugado no lineal
• Algoritmo de Levenberg-Marquardt
• Método de Broyden–Fletcher–Goldfarb–Shanno o BFGS
• Evolución diferencial
• Búsqueda de patrones (optimización)
• CMA-ES

Referencias

1. • Powell, Michael JD (1973). "Sobre direcciones de búsqueda para algoritmos de minimización". Programación matemática . 4 : 193–201. doi :10.1007/bf01584660. S2CID  45909653.
   • McKinnon, KIM (1999). "Convergencia del método simplex de Nelder-Mead a un punto no estacionario". Revista SIAM sobre optimización . 9 : 148–158. CiteSeerX  10.1.1.52.3900 . doi :10.1137/S1052623496303482.(Resumen del algoritmo en línea).
2. • Yu, Wen Ci. 1979. "Base positiva y una clase de técnicas de búsqueda directa". Scientia Sinica [ Zhongguo Kexue ]: 53—68.
   • Yu, Wen Ci. 1979. "La propiedad convergente de la técnica evolutiva simplex". Scientia Sinica [ Zhongguo Kexue ]: 69–77.
   • Kolda, Tamara G. ; Lewis, Robert Michael; Torczon, Virginia (2003). "Optimización por búsqueda directa: nuevas perspectivas sobre algunos métodos clásicos y modernos". SIAM Rev . 45 (3): 385–482. CiteSeerX  10.1.1.96.8672 . doi :10.1137/S003614450242889.
   • Lewis, Robert Michael; Shepherd, Anne; Torczon, Virginia (2007). "Implementación de métodos de búsqueda de conjuntos generadores para la minimización linealmente restringida". SIAM J. Sci. Comput . 29 (6): 2507–2530. Bibcode :2007SJSC...29.2507L. CiteSeerX  10.1.1.62.8771 . doi :10.1137/050635432.
3. Nelder, John A.; R. Mead (1965). "Un método simplex para la minimización de funciones". Computer Journal . 7 (4): 308–313. doi :10.1093/comjnl/7.4.308.
4. Spendley, W.; Hext, GR; Himsworth, FR (1962). "Aplicación secuencial de diseños símplex en optimización y operación evolutiva". Technometrics . 4 (4): 441–461. doi :10.1080/00401706.1962.10490033.
5. • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.5. Método símplex descendente en multidimensiones". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
6. Nash, JC (1979). Métodos numéricos compactos: álgebra lineal y minimización de funciones . Bristol: Adam Hilger. ISBN 978-0-85274-330-0.

Lectura adicional

• 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 multivariadas no uniformes". 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. pp. 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 optimización sin restricciones . Nueva York: Academic Press. págs. 13–28. ISBN 978-0-12-512250-4.

Enlaces externos

• Explicación y visualización de Nelder–Mead (Downhill Simplex) con la función banana de Rosenbrock
• John Burkardt: Código Nelder–Mead en Matlab: tenga en cuenta que la función fminsearch de Matlab también implementa una variación del método Nelder–Mead.
• Optimización de Nelder-Mead en Python en la biblioteca SciPy.
• nelder-mead: una implementación en Python del método Nelder–Mead
• NelderMead() - Una implementación de Go/Golang
• SOVA 1.0 (freeware): optimización simplex para diversas aplicaciones
• [1] - HillStormer, una herramienta práctica para la optimización simplex no lineal, multivariada y lineal restringida por Nelder Mead.