Método Nelder-Mead

Algoritmo de optimización numérica

Una iteración del método Nelder-Mead en un espacio bidimensional.

Busque en la función banana de Rosenbrock

Buscar sobre la función de Himmelblau

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

El método 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 el máximo de una función objetivo en un espacio multidimensional. Es un método de búsqueda directa (basado en comparación de funciones) y a menudo se aplica a problemas de optimización no lineales para los cuales es posible que no se conozcan las derivadas. 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 simplex , que es un politopo especial de n  + 1 vértices en n dimensiones. Ejemplos de simples incluyen un segmento de línea en un espacio unidimensional, un triángulo en un espacio bidimensional, un tetraedro en un espacio tridimensional, etc.

El método se aproxima a 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 las 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 desde el punto de vista computacional y posiblemente lleve 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 hasta el óptimo propuesto puede ser alto.

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 de prueba y reemplazar uno de los puntos de prueba antiguos por el nuevo, y así avanza 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, entonces podemos intentar estirarnos 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 "Recetas numéricas": ^[5]

El método simplex cuesta abajo ahora requiere una serie de pasos, la mayoría de los cuales simplemente mueven el punto del simplex donde la función es mayor (“punto más alto”) a través de la cara opuesta del simplex hasta un punto más bajo. Estos pasos se denominan reflexiones y se construyen para conservar el volumen del simplex (y, por tanto, mantener su no degeneración). Cuando puede hacerlo, el método expande el simplex en una dirección u otra para dar pasos más grandes. Cuando llega al “fondo del valle”, el método se contrae en dirección transversal e intenta fluir valle abajo. Si hay una situación en la que el simplex intenta “pasar por el ojo de una aguja”, se contrae en todas direcciones, metiéndose alrededor de su (mejor) punto más bajo.

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] Desde 1979 se conocen mejoras modernas con respecto a la heurística de Nelder-Mead. ^[2]

Existen muchas variaciones dependiendo de la naturaleza real del problema que se resuelve. Una variante común utiliza un simplex pequeño de tamaño constante que sigue aproximadamente la dirección del gradiente (lo que proporciona el descenso más pronunciado ). Visualice un pequeño triángulo en un mapa de elevación girando hacia abajo por un valle hasta un fondo local. Este método también se conoce como método del poliedro flexible . Sin embargo, esto tiende a funcionar mal frente al 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 Nelder-Mead aplicado a la función 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}).}$

Compruebe si el método debe detenerse. Consulte Terminación (a veces llamada "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 calcule 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 simplex 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 "siguiente" 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 calcule 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 contratado 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 calcule 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 contratado 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. Reducir

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 , al ser el vértice con mayor valor asociado entre los vértices, podemos esperar encontrar un valor menor 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}}$

En cuanto 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}}$

Finalmente, el encogimiento maneja el raro caso de que la contracción desde el punto más grande aumente , algo que no puede suceder 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 no reducir el tamaño simplex, e implementó una verificación de que el tamaño realmente se reduce. ^[6] ${\displaystyle f}$

simplex inicial

El simplex inicial es importante. De hecho, un simplex inicial demasiado pequeño puede conducir a una búsqueda local y, en consecuencia, el NM puede atascarse más fácilmente. Entonces este simplex debería depender de la naturaleza del problema. Sin embargo, el artículo original sugirió un simplex donde un punto inicial se da como , y los demás se generan con un paso fijo a lo largo de cada dimensión por turno. Por tanto el método es sensible al escalamiento de las variables que lo 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 muestral de los valores de función del simplex actual. Si estos caen por debajo de cierta tolerancia, entonces el ciclo se detiene y el punto más bajo del simplex se devuelve como óptimo propuesto. Tenga en cuenta 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 añade la prueba de contracción como otro criterio de terminación. ^[6] Tenga en cuenta que los programas terminan, mientras que las iteraciones pueden converger.

Ver también

• Optimización sin derivados
• COBILA
• NUEVOUOA
• LINCOA
• Método de gradiente conjugado no lineal
• Algoritmo de Levenberg-Marquardt
• Método 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. "Bases positivas y una clase de técnicas de búsqueda directa". Scientia Sínica [ Zhongguo Kexue ]: 53—68.
   • Yu, Wen Ci. 1979. "La propiedad convergente de la técnica evolutiva simplex". Scientia Sínica [ 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; Pastor, Ana; Torczon, Virginia (2007). "Implementación de métodos de búsqueda de conjuntos generadores para minimización restringida linealmente". SIAM J. Ciencias. Computación . 29 (6): 2507–2530. Código Bib : 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". Diario de informática . 7 (4): 308–313. doi :10.1093/comjnl/7.4.308.
4. Spendley, W.; hexadecimal, GR; Himsworth, FR (1962). "Aplicación Secuencial de Diseños Simplex en Optimización y Operación Evolutiva". Tecnometría . 4 (4): 441–461. doi :10.1080/00401706.1962.10490033.
5. • Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.5. Método simplex cuesta abajo en multidimensiones". Recetas numéricas: el arte de la informática 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.

Otras lecturas

• Avriel, Mardoqueo (2003). Programación no lineal: análisis y métodos . Publicación de Dover. ISBN 978-0-486-43227-4.
• Coope, ID; Precio, CJ (2002). "Bases positivas en la 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 suaves". Optimización práctica . Nueva York: Academic Press. págs. 93–96. ISBN 978-0-12-283950-4.
• Kowalik, J.; Osborne, señor (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 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 (software gratuito): optimización simplex para diversas aplicaciones
• [1] - HillStormer, una herramienta práctica para optimización simplex no lineal, multivariada y lineal restringida de Nelder Mead.