Optimizacion no lineal UNIVERSIDAD EXPERIMENTAL POLITECNICA DE LA FUERZA ARMADA NACIONAL (UNEFA)

REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA  DEFENSA

UNIVERSIDAD EXPERIMENTAL POLITECNICA DE LA FUERZA ARMADA NACIONAL (UNEFA)

SEDE SAN TOME, ESTADO ANZOÁTEGUI

[pic 1]

San Tome, 07 de noviembre de 2016

Introducción

A continuación mostraremos dos métodos analíticos para optimizar una función real en el caso que no existan restricciones y en caso de que si existan restricciones sobre el dominio de la función y cuando la función admite segundas derivadas continuas. Esta técnica generaliza la técnica de optimización de funciones en una variable utilizando cálculo diferencial: primeramente se determina cuáles son los candidatos a óptimos, y posteriormente se aplica un criterio basado en la segunda derivada para determinar si corresponden a un máximo o mínimo relativo.

Definiremos los métodos de Newton (Newton Raphson), Método de Gradiente Conjugado, Método de Davidon – Fletcher – Powell en el caso de los métodos de optimización sin restricciones.

En el caso de métodos con restricciones definiremos función de Lagrange. Direcciones factibles, condiciones de Karus-kuhn Tucker, tipos de programación y método de penalización.

Metodo de Optimizacion sin Restricciones

Método de Newton (Newton Raphson). 

El método de Newton Raphson, es un método iterativo, lo cual, es uno de los métodos más usados y efectivos. 

Por lo tanto, no trabaja sobre un intervalo sino que se basa su fórmula en un proceso iterativo.

Un proceso iterativo, significa el repetir una actividad con la intención de alcanzar una meta deseada, objetivo o resultado.

Podríamos decir también, que el método de newton es un método abierto, lo cual parte de un valor inicial que se introduce en una expresión relacionada con la ecuación, obteniendo así un resultado. Ese resultado se introduce en la misma expresión, obteniendo un nuevo resultado y así sucesivamente.

Supongamos que tenemos la aproximación   [pic 2] a la raíz  [pic 3]  de  [pic 4],
[pic 5]
Trazamos la recta tangente a la curva en el punto  [pic 6]; ésta cruza al eje  [pic 7]  en un punto  [pic 8] que será nuestra siguiente aproximación a la raíz  [pic 9].
Para calcular el punto  [pic 10], calculamos primero la ecuación de la recta tangente. Sabemos que tiene pendiente

Y por lo tanto la ecuación de la recta tangente es:

Hacemos  [pic 13]:

Y despejamos  [pic 15]:

Que es la fómula iterativa de Newton-Raphson  para calcular la siguiente aproximación:

Note que el método de Newton-Raphson  no trabaja con intervalos donde nos asegure que encontraremos la raíz, y de hecho no tenemos ninguna garantía de que nos aproximaremos a dicha raíz. Desde luego, existen ejemplos donde este método no converge a la raíz, en cuyo caso se dice que el método diverge. Sin embargo, en los casos donde si converge a la raíz lo hace con una rapidez impresionante, por lo cual es uno de los métodos preferidos por excelencia.

Método de Gradiente Conjugado.

El Método de Gradiente Conjugado aplica a sistemas de ecuaciones lineales como Ax=b en los cuales A es simétricas y definidas positivas. En este método las direcciones V(k), que forman un sistema A- ortogonal se determinan una a una en cada iteración. 

Por lo tanto así sucesivamente el teorema pasa a ser un algoritmo. 

Método de Davidon – Fletcher – Powell

El método de Davidon-Fletcher-Powell tiende a tener un buen comportamiento en una amplia variedad de problemas prácticas. Una de la dificultad prácticas común es la tendencia de A(k+1) a estar mal condicionada, lo que causa una mayor dependencia a un procedimiento de re inicialización. Este es un método que minimiza una función f en Rn. Genera aproximaciones sucesivas de la inversa del Hessiano de la función f.

Algoritmo

Paso 1:

Elegir un punto inicial

X(0) y tolerancias €1,€2 y €3

Paso 2:

Encontrar

∇f (X(0)) y hacer: s(0)= −∇f(X(0))

Paso 3:

Encontrar

λ (0) tal que: f (X(0) + λ(0) s(0)) se minimice con una tolerancia €1.

Hacer X (1)=X(0) + λ(0) s(0) y k= 1

Calcular: ∇f(X(1))

Paso 4:

Hacer: s(k) = −A(k) ∇f(x(k))

Paso 5:

Encontrar: λ(k) tal que:

f(X(k) + λ(k) s(k)) sea mínima con una tolerancia €1

Hacer X(k+1) = X(k) + λ(k) s(k)

Paso 6:

¿Es||X(k+1) − X(k)||   ≤ €2 o ||∇f(X(k+1))|| ≤3?

            ||X(k)||            

Si es así, terminar. ELSE k=k+ 1. GOTO Paso 4.

Método de Optimización con Restricciones

Es el paso de optimización a una función objetivo con respecto a algunas variables con restricciones en las mismas. La función objetivo o bien sea una función de coste o de energía que debe ser minimizada, o una función de recompensa o utilidad, que ha de ser maximizado.

Las restricciones de optimización se dividen en 2 partes las cuales son:

• Las duras las cuales establecen condiciones para las variables que se requieren estar satisfecha,
• Las blandas que tienen algunos valores de  variables que están penalizados en la función objetivo  y asentados ​​en la medida en que, las condiciones en las variables no son satisfecho.

Función de Lagrange

Es un procedimiento que se realiza para encontrar los máximos y mínimos de funciones de múltiples variables sujetas a restricciones.

...