Metodo De Nelder-Mead

MÉTODO DE NELDER-MEAD

Nelder-Mead desarrollaron un método para hallar el mínimo local de una función de varias variables. Método que utiliza un tipo de cuerpo geométrico llamado simplex, que para el caso del plano es un triángulo y para el espacio tridimensional es un tetraedro.

En el caso de dos variables el método consiste en comparar los valores de la función en los vértices del triángulo y sustituir el peor vértice por un vértice nuevo. Por tanto, se forma un nuevo triángulo y la búsqueda continúa. De este modo, se genera una sucesión de triángulos que pueden tener formas diferentes y en los que los valores de la función van decreciendo.

TRIANGULO INICIAL

Sea f(x,y) la función que se desea minimizar. Se parte de un triángulo inicial cuyos vértices son:

PUNTO MEDIO DEL LADO BUENO

El siguiente paso es calcular el punto medio del segmento que une O con B:

REFLEXIÓN USANDO EL PUNTO R

Al movernos de P hacia O o B la función decrece, por tanto, la f (x,y) toma valores menores en puntos alejados del peor vértice P que están situados al otro lado del segmento que une O con B. Lo que se hace es tomar un punto de prueba R que se obtiene reflejando el triángulo a través del lado OB.

El punto R se determina por la unión del punto M (del lado OB) con P, segmento denominado d, encontrando R de la extensión del segmento d hacia el otro lado de M la misma distancia d, originando el nuevo triángulo OBR.

Cálculo de R:

EXTENSIÓN USANDO EL PUNTO E

Si el valor de la función en el punto R es menor que el valor en el punto P, entonces es la dirección correcta hacia el mínimo. Puede ser que el mínimo se halle un poco más allá del punto R, por tanto, se extiende una distancia adicional d, el segmento que une M y R hasta un punto E y de esa forma se obtiene un triángulo extendido OBE. Si el valor de la función en E es menor que en R , entonces se halla un vértice mejor que R. La fórmula para calcular E es:

CONTRACCIÓN USANDO EL PUNTO C

Si los valores de la función en R y P son iguales, o en P es menor que en R, entonces debe probarse otro punto. Considérese los puntos medios C1 y C2 de los segmentos PM y MR, respectivamente, el punto en que la función tome un valor menor será C y el nuevo triángulo será OBC.

Nota : para dimensiones superiores, la elección de C1 y C2 es importante.

ENCOGIMIENTO HACIA ‘O’.

Si el valor de la función en C no es menor que en P, entonces se tiene que escoger el triángulo en la dirección O. El punto B se reemplaza por M y P se reemplaza por S que es el punto medio de OP.

DECISIONES LÓGICAS

...