Optimización multivariable irrestricta

Optimización Multivariable irrestricta

Métodos Directos

Optimización Multivariable Irrestricta

1

Método Simplex
El método Simplex Secuencial utiliza una figura geométrica regular para seleccionar puntos en los vértices de una figura en los que se debe evaluar la función. En dos dimensiones la figura es un triangulo equilatero, en tres dimensiones es un tetrahedro regular. La nuevadirección de búsqueda se toma desde el vértice con el peor valor de función, entonces las direcciones de búsqueda cambian, pero el tamaño del paso es fijo para un determinado simplex (factor de escala).

En cada iteracióon, para minimizar f(x), se evalua la función en cada uno de los tres vértices del triángulo. La nueva dirección de búsqueda se orienta desde el punto con el peor valor de funcióna través del centroide del simplex. Se selecciona el nuevo punto en esta dirección reflejada, preservando la forma geometrica. La función objetivo se evalúa en este nuevo punto y se calcula una nueva dirección de búsqueda. El método procede rechazando un vertice por vez hasta que el simplex encierre el óptimo
Optimización Multivariable Irrestricta 2

Regla 1: Si el peor vértice fue generadoen las iteraciones previas, entonces se elige para reflejar el siguiente vértice con el siguiente valor de funcion mas alto. Regla 2: Si un vértice permanece sin cambiar por mas de M iteraciones, reducir el tamaño del simplex por algún factor. M=1.65*N+0.05*N2 Donde N es la dimension del problema y M se debe redondear al entero mas próximo. Regla 3: Criterio de terminación: La búsqueda finalizacuando el simplex es muy pequeño ó cuando el desvío estándar de valores de función en los vértices de pequeño. Se debe entonces especificar el parámetro de terminación. La implementación del algoritmo requiere solo dos tipos de cálculos: (1) Generación de un simplex regular dado un punto base y un factor de escala apropiado y (2) cálculo del punto reflejado

Optimización Multivariable Irrestricta3

Algoritmo de Powell
El algoritmo de Powell ubica el mínimo de una función f por búsquedas unidimensionales secuenciales desde un punto inicial x0 a lo largo de un conjunto de direcciones conjugadas generadas por el algoritmo

Un posible método de búsqueda podría comenzar con dos direcciones no necesariamente conjugadas ξ1(0)y ξ2(0). En la primer etapa estas podrían ser las direccionesde los ejes coordenados. Entonces llevamos a cabo nuestra búsqueda unidimensional partiendo desde un punto base elegido arbitrariamente x0(0) y encontrando un punto mejorado x2(0).Luego definimos una dirección de búsqueda favorable µ(0)=x2(0)- x0(0) . Donde µ(0) es la dirección desde el punto base al punto final de la búsqueda en una dimensión
Optimización Multivariable Irrestricta 4

Aquí notenemos la seguridad de que µ sea una direccióon que pase a través del óptimo incluso si la función fuese cuadrática.. Hagamos ahora otra búsqueda a lo largo de µ(0)alcanzando un punto mejorado x0(1), el punto base para la segunda etapa de la búsqueda. Usemos ahora las direcciones ξ1(1)= ξ2(0) y ξ2(1)= µ(0) en nuestra segunda etapa. Si X2(1)es el óptimo encontrado lluego de pasar por estas dosnuevas direcciones, entonces la direccióon µ(1)=x2(1)-x0(1) pasará a través del óptimo de una función cuadrática. Por supuesto, si la función no es cuadrática, entonces µ(1) no necesariamente pasará por el óptimo, pero probablemente sea una dirección de búsqueda favorable. Deben repetirse entonces las iteraciones. El método de Powell tiene ventajas respecto de lo presentado anteriormente. Puede serresumido como sigue para una búsqueda unidimensional. Etapa 1: Comenzando con el mejor valor previo x0(k) y una serie de direcciones de búsqueda linealmente independientes, ξ1(k), ξ2(k) ,......ξn(k), comenzar la búsqueda buscando la posición del óptimo a lo largo de la línea que pasa a través de x0(k) la que es paralela a ξ1(k). Sea este punto óptimo x1(k), comenzamos una segunda búsqueda desde...