Búsqueda del gradiente

MÉTODO DE BÚSQUEDA DEL GRADIENTE

Este método permite asegurar la búsqueda del punto óptimo (si existe), ya que en cada iteración redirecciona el vector de búsqueda, lo que otros métodos (como Newton Raphsón) no hacen.
Sirve para optimizar problemas de funciones no lineales sin restricciones con dos o más variables.
El método se desarrolla del modo siguiente:

1.- Elija un punto dearranque Xo, y un valor de detención ε (por lo regular vale entre 0.001 y 0.000001).
2.- Valúe el vector gradiente de la función en el punto actual.
3.- Cambie la función a términos de t, utilizando la siguiente expresión:
x´=x´+t▼f(x)
4.- Sustituya el resultado anterior en la función original f(x).
5.- Derive el resultado del paso anterior con respecto de t e iguale con cero para encontrar elóptimo t*.
6.- Genere el nuevo punto utilizando la expresión:
x´=x´+t*▼f(x)
7.- Aplique la regla de detención dada por:
Si se cumple que [pic]


Entonces pare, y el último punto encontrado es el óptimo,
De lo contrario repita el proceso tantas veces como sea
Necesario hasta queesta regla se cumpla.


Ejemplo.- Maximice la siguiente función:




1.-Punto de arranque Xo= (100,100) valor de detención ε = 10 -3

2.-Evaluar el gradiente de f(x) en el punto actual que es Xo.

[pic] entonces ▼f(Xo) = (-100,250)








3.- Cambiar a términos de x´=x´+t▼f(x)

[pic]

4.- sustituir el resultado anterior en la función original f(x)




UB= -2(-100t + 100)2 – 0.5 (250t + 100)2 + (-100t + 100)(250t + 100) + 200(-100t + 100) + 250 (250t + 100) – 55700.
UB = -2(10000t2 -20000t + 10000) – 0.5(62500t2 + 50000t + 10000) + (-25000t2 -10000t + 25000t + 10000) -20000t + 20000+ 62500t + 25000 – 55700.
UB = -20000t2 + 40000t -20000 – 31250t2 -25000t – 5000 – 25000t2 -10000t + 25000t + 10000 -20000t + 20000 + 62500t + 25000 – 55700.
UB =t2(-20000-31250-25000) + t(40000 -25000 – 10000 + 25000 -20000 + 62500) -20000 – 5000 + 10000 + 20000 + 25000 – 55700.
UB = -76250 t2 + 72500 t -25700

5.- Derivar el resultado anterior con respecto de t e igualar con cero.

dUB/dt = -152500t + 72500 = 0

Despejando a t se obtiene t* que t* = 0.4754098

6.- Generar el nuevo punto con x´=x´+t*▼f(x)
Así se tiene x´= ( 100,100) + 0.4754098(-100, 250)

X1 = (52.46, 218.85)

7.- Probar la regla de detención dada por
[pic]


F(Xo) = -2(100)2 – 0.5(100)2 + 100*100 + 200*100 + 250* 100 – 55700 = -25700
F(X1) =-2(52.46)2 – 0.5(218.85)2 + 52.46*218.85 + 200*52.46 + 250* 218.85 – 55700
= -8466.3934

Así se tiene │ -25700 – (-8466.3934│ =│ -17233.8066 │ > 0.001 hay que seguir iterando.





2.-Evaluar el gradiente de f(x) en el punto actual que es Xo.


X0 = (52.46, 218.85)




entonces ▼f(Xo) = (209.01,83.61)


3.- Cambiar a términos de x´=x´+t▼f(x)


[pic]


4.- sustituir el resultado anterior en la función original f(x)






UB = -2(209.01t + 52.46)2 – 0.5 (83.61t + 218.85)2 +(209.01t +52.46)(83.61t + 218.85) + 200(219.01t + 52.46) + 250 (83.61t + 218.85) – 55700.

UB = -2(43685.1801t2 +21929.3292t + 2752.0516) – 0.5(6990.6321t2 +36596.097t + 47895.3225) + (17475.3261t2 +45741.8385t + 4386.1806t + 11480.871) +43802t +10492+ 20902.5t + 54712.5 – 55700.

UB = -87370.3602t2 - 43858.6584t -5504.1032 – 3495.31605t2 -18298.0485t – 23947.66125 +17475.3261t2 +45741.8385t +4386.1806t + 11480.871 +43802t +10492+ 20902.5t + 54712.5 – 55700.

UB = t2(-87370.3602– 3495.31605+17475.3261) + t(- 43858.6584-18298.0485+45741.8385+4386.1806+43802+20902.5) -5504.1032– 23947.66125+ 11480.871+10492+ 54712.5 – 55700.

UB = -73390.35015 t2 + 52675.8122 t -8466.39345

5.- Derivar el resultado anterior con respecto de t e igualar con cero.

dUB/dt = -146780.7003t +...