PRINCIPIOS DE OPTIMIZACION

POR: 

MARRASQUIN GUERRERO KARLA ESTEFANY                                  IX semestre A

RIVERA FUENTES ALLISON BETSABE                                               2 do parcial

RODRIGUEZ HOLGUIN KAREN JULEISY                                       

SALCEDO DELGADO LEONARDO JAVIER

CAPITULO 5 

PRINCIPIOS DE LA OPTIMIZACION

INTRODUCCIÓN:

En el análisis y diseño de sistemas de ingeniería ocurren situaciones que provocan efectos conflictivos.

5.1 TÉCNICAS DE OPTIMIZACION

FUNCIÓN OBJETIVO: Maximizar algún beneficio o salidas del sistema, o de minimizar los costos o entradas al proceso.

1.  Balance de materia
2. Balances de eneria
3. Ecuaciones de diseño
4. Estipulaciones de algunas variables

 Se puede clasificar el problema mediante el tipo de relaciones que definen la función objetivo y las restricciones del sistema.

5.2 OPTIMIZACION DE UNA VARIABLE

Se puede usar los principios de calculo diferencial. 

- La derivada de la función con respecto a la variable de interés  igualada a cero proporciona el máximo o el mínimo que se busca.

En el caso que los requerimientos no se cumplan se aplica:

- Técnicas de búsqueda: se basa en el concepto de eliminación de regiones. la ´´función objetivo´´ se evalúa en  varios puntos y se rechaza la región que contenga los peores valores. (el proceso se repite de tal forma que la región de búsqueda se va aislando hasta que contenga el punto optimo)

FUNCIÓN OBJETO para un problema de optimizacion debe ser UNIMODAL para garantizar el valor optimo global mediante un método numérico

Las funciones NO UNIMODAL conducen a un valor optimo local.

FUNCIONES UNIMODALES

FUNCIONES NO UNIMODALES

5.3 El Método De La Sección Dorada

Uno de los métodos más efectivos para optimizar problemas de una variable es el conocido como sección Dorada o SECCION ÁUREA.

El método se basa en la colocación de puntos de búsquedas simétricos, de tal manera en cada iteración, el punto que se conserva sirve como base para la selección del nuevo punto, el cual a su vez debe conservar la simetría original, pero acotando la solución óptima dentro de un intervalo de una búsqueda menor

La idea básica es economizar el número de evaluaciones de función y acotar la solución óptima en intervalos anidados sucesivos. Esto se logra evaluando la función objetivo f(x) en dos puntos anteriores de cada intervalo:  _{(Lado Izquierdo)} y r_{i ( lado derecho)} contenidos en [ai,  ] o  [ r_i, b_i ] del problema, dependiendo  de qué zona sea lo que contenga el peor punto de los avaluados.

5.3.1 DEDUCCIÓN DEL MÉTODO

Al evaluar la función objetivo en cada uno de estos dos puntos interiores, se comparan los valores obtenidos, y se rechaza la región comprendida a la izquierda de o la comprendida a la derecha  de  dependiendo de cuál de estos puntos generó{o el peor valor de la función objetivo

•   Las dos primeras iteraciones el método de sección dorada, suponiendo que el punto es peor que el punto Io

La función evaluada en  proporciona un  peor valor de la función objetivo que el obtenido con el punto  ,por lo que se rechaza  la región 

5.3.2 REDUCCIÓN DE INTERVALOS

La contracion que se logra en el espacio de búsqueda con el método de sección dorada esta dada por

Donde:

n= es elnumero de evaluaciones, equivalente a n-2 iteraciones ( recordar que este número de iteraciones implica que la colabracin de puntos iniciales se ha definido como la iteracion 0)

Esta relación puede servir para establecer el numero de iteraciones que se requiere en un problema dado para alcanzar una aproximacion deseado en el valor optimo

ejemplo: Aplicación Del Método De La Sección Dorada

Encontrar el mínimo de la función f(x)= x² – x en el intervalo (0.2)

Usar 4 iteraciones.

SOLUCION:

Podemos predecir primero el grado de reducción del intervalo original para las cuatros iteraciones que se desean, las cuales equivalen a n=6 evaluaciones de función. Por lo tanto,

O 9% del intervalo original.

ITERACCIÓN 0

Colocación de puntos iniciales

El peor punto es r₀ por lo que se rechaza el intervalo 

como se muestra a continuación

   ITERACCION 1

El intervalo remanente (a₁ , b₁) es (0, 1.236)

El punto   Io = 0.754 se convierte en r1 , por lo que debemos evaluar el punto I1 para esta iteración

 ITERACION 2

Este es un peor punto que el anterior, ya que f(I1) mayor f(r2)  por lo que debe eliminarse la región comprendida a la izquierda de I2

  ITERACION 3

ITERACCION 4

Eliminar (0.292, 0.403)

Hasta el nivel, el óptimo se ha acotado en el intervalo (0.403, 0.584) el cual corresponde al 9% del intervalo original. El mejor punto obtenido en cuatro iteraciones es  

x*=0.472

LA SOLUCION EXACTA ES   X* =0.5

5.4 METODO FIBONACCI

Se diferencia de la sección dorada, ya que el factor de concentración τ_i no es constante y cambia con cada interacción.

Considerar la siguiente figura.

Supongamos que se rechaza la región derecha del intervalo (r_i-1, b_i-1), y analicemos las dos opciones de cambio para el punto remanente l_i-1

ANÁLISIS DE HACER l_i-1= l_i

ANALISIS DE HACER l_i-1= r_i

Por lo cual se requiere de una condición inicial o una terminal.

Supongamos que n ≥ 3 es un número fijo de evaluaciones de función permisibles, se tiene el siguiente esquema  de evaluaciones de función: 

Examinar la penúltima interacción. Para simplificar, hacer que τ_n-3 = β. (ver fig.). Con objeto de maximizar la región de rechazo en la última interacción (y por tanto minimizar la longitud del ultimo intervalo remanente), conviene escoger β de tal manera que el punto r_n-2 quede exactamente a la mita del intervalo (a_n-2, b_n-2), es decir 

1 - β = 2β – 1

De donde β = 2/3 = τ_n-3

Lo cual implica que τ_n-2 = (1+ε)/2, donde ε << 1. Por lo tanto, podemos usar τ_{n-3 =} 2/3 como la condición terminal para la ecuación 

de la cual se obtiene la forma recursiva para la evaluación de  τ_i-1

Aplicando esta relación, se obtienen los siguientes valores:

Donde F_i son los números de Fibonacci, los cuales se obtienen al sumar los dos anteriores:

CORRECCION DEL INTERVALO

Después de n – 2 iteraciones, lo cual implica n evaluaciones de función, el intervalo original se reduce a una fracción equivalente a

CONSTRUCCION DE BUSQUEDA MEDIANTE FIBONACCI

Para n evaluaciones de función, en general, se construye la siguiente secuencia:

Consideremos el caso en que n = 6 evaluaciones de función (equivalentes a 4 iteraciones)

Con esta secuencia de valores de τ_i se construye la búsqueda de Fibonacci, similar a la sección dorada, solo que ahora τ varía en cada interacción.

·       El método Fibonacci es ligeramente superior al de sección dorada ya que se logra una reducción de intervalos

·       A diferencia de la sección dorada, en Fibonacci es necesario que se fije el número de intervalos antes de empezar a aplicarlo, ya que a partir de esto se evalúa el parámetro inicial para τ₀

APLICACIÓN DEL METODO

Minimizar la función f(x) = (x-4)² haciendo una búsqueda en el intervalo (0,9). Usar 2 iteraciones.

SOLUCIÓN:

Para n-2 iteraciones se requiere de n = 4 evaluaciones de función.

Sabemos que τ_n-2 = τ₂ = ½, a partir de lo cual se construye la secuencia de valores de τ_i que se van a usar en cada iteración i:

Comenzar colocando los primeros puntos

ITERACION 0

Evaluamos es la función inicial f(x) = (x-4)²  y obtendremos los valores de

·       f(l₀) = 0.16

·       f(r₀) = 1.96

Graficamos:

Y se rechaza el lado derecho [r_0, b₀] = [5.4; 9]

ITERACION 1

Para esta iteración usar 

El punto que quedo sin eliminar en el anterior, que era el izquierdo, se transforma en el punto derecho para esta iteración

l₀  →  r₁ = 3.6

Entonces el punto izquierdo será 

Y reemplazando en la función f(x) = (x-4)²

f(l₁)= 4.84 y graficamos:

Y se rechaza el lado izquierdo [l_1, a₁] = [1.8; 0]

ITERACION 2

Es la última iteración que se ha fijado, en la cual el intervalo remanente es [a_2, b₂] = [1.8; 5.4]

Y r₁ pasa a ser l₂ = 3.6

Como se trata de la última iteración el nuevo punto r2 debe coincidir con el punto l2.

Y evaluando en nuestra función obtendremos

f(x) = (x-4)²

f(3.61)= 0.1521 y graficamos:

En esta última iteración podemos eliminar la mitad de la región remanente evaluando la función en el punto l2 + E, donde E = 0,001

CONCLUSION:

El método de Fibonacci con 2 iteraciones termina con un aproximado del optimo x= 3.6.

Se detecta que el óptimo está comprendido entre el 3.6 y 5.4. La solución exacta implica x= 4