Metodos numericos de optimizacion no lineal

Índice
Introducción 3
Capítulo I
Método del Gradiente 4
Método de Newton 6
Direcciones Conjugadas 8
Método del Gradiente Conjugado 10
Método de la Métrica Variable 13
Método de Davidon-Fletcher-Powell 14
Algoritmo de Cuasi-Newton 16
Referencias 18

Introducción

Los métodos numéricos son técnicas mediante lascuales es posible formular problemas matemáticos de tal forma que puedan resolverse usando operaciones aritméticas-algorítmicas. Hay muchos tipos de métodos numéricos, estos son herramientas muy poderosas para la solución de problemas. Pueden manejar sistemas de ecuaciones grandes, no linealidades y geometrías complicadas, comunes en la ingeniería.
Desde un punto de vista práctico, encontrar elmínimo o máximo global de una función no-lineal cualquiera es un problema abierto en matemáticas ya que los métodos existentes sólo obtienen mínimo locales.
Un punto x es un mínimo local de f en Rn si existe r>0 tal que: f(x)≤f(x) para x-x≤ r. El mínimo global de f será el mínimo local de menor valor de la función objetivo.
Sin embargo, existe toda una metodología que permite tratar problemas deoptimización no-lineales con restricciones como problemas de optimización no-lineales sin restricciones
Entonces, para obtener el mínimo local se debe resolver un sistema de ecuaciones no lineales, en general complejo. Surge de esta forma la necesidad de aplicar métodos numéricos que estudiaremos a continuación.

Capítulo I: Métodos

* Método del Gradiente:

Si f es una función de dosvariables x y y existen, entonces el gradiente de f denotado por ∇f esta definido por:
∇f(x, y) = fx(x, y)i + fy(x, y)j
Una herramienta utilizada para estudiar mínimos es la serie de Taylor, que es una aproximación polinomial dada por:
f(x+p)=c0+c1p+c2p2+c3p3+c4p4+c5p5+ · · ·
donde x es un punto y p es un incremento de x en alguna dirección.
Existen condiciones necesarias para determinar unmínimo, estas están relacionadas con el gradiente ∇f y el Hessiano ∇2f.
* Condición necesaria de primer orden
Si x* es un mínimo local y f es diferenciable en una vecindad de x* entonces ∇f(x*)=0.
Supongamos por contradicción que ∇f(x*)≠0. Definimos el vector p=-∇f(x*) y notamos que:
pT∇f(x*)=- ∇f(x*)2<0
Dado que ∇f es continuo cerca de x*, existe un escalar T>0 tal que:pT∇fx*+tp<0 ∀ t∈[0, T]
Para algún t∈[0, T], tenemos que la serie de Taylor nos da:
f(x*+tp)=f(x*)+tpT∇f(x*+tp)
f(x*)-tpT∇f(x*+tp)>f(x*)
Por lo tanto f(x*+tp)<f(x*) para toda t∈(0, T]. Tenemos una contradicción, hemos encontrado una dirección que se aleja de x* y f decrece, por lo cual, x* no es un mínimo local. Llamaremos x* a un punto estacionario si ∇f(x*)=0.

* Condición necesaria desegundo orden
Si x* es un mínimo local de f y ∇2f es continua en la vecindad de x*, entonces
∇fx*=0 y ∇2f2(x*) es definida semi positiva.
Por contradicción, asumimos que ∇2f(x*) no es definido positivo. Entonces seleccionamos un vector p tal que pT∇2f(x*)p<0 para todo t ∈ [0, T].
f(x*+tp)=f(x*)+ tpT∇f(x*+tp)+12t-2pT∇2f(x*+tp)p
fx*+12t-2pT∇2fx*+tpp>fx*
Por lo tanto fx*+tp<fx* por lo cualf(x*) no es un mínimo.
Ejemplo:
Dada la función f(x, y)=x2+y2+5xy+2x-3y-20 determinar: La expresión del gradiente ∇f(x, y), la expresión del Hessiano ∇2f(x, y) y el punto de inflexión.

El vector gradiente queda como:
∇f(x, y)=2x+5y+22y+5x-3
La matriz Hessiana es ∇2f(x, y)=2552
El punto extremo lo calculamos resolviendo el sistema de ecuaciones
2552xy=-23

La solución es x=1921 yy=-1621 . El determinante del Hessiano det(∇2f(x, y)) = -21 por lo cual se trata de un máximo.

* Método de Newton:

Consideremos que la función f es de clase dos, es decir que la segunda derivada puede ser calculada. La idea consiste en reemplazar en la vecindad del punto xk de la función f por una aproximación cuadrática q(x) dada por
q(x)=f(xk)+∇fT (xk)(x-xk)+12(x-xk)T∇2f(xk)(x-xk)...