Optimización: Descenso de Gradiente

Video

Introducción

¿A qué le llamamos derivada?

El algebra y la geometría nos describen cantidades estáticas, es decir, cantidades que no necesariamente sufrirán cambios respecto a otras como el cambio de una cantidad determinada, por ejemplo, ante el tiempo o el movimiento. Este tipo de situaciones pueden encontrarse en diversos fénomenos, por ejemplo: El movimiento de los planetas alrededor del sol, la propagación de una epidemia o incluso hasta en lo más cotidiano, cómo determinar la ruta más corta en un viaje.

Para describir a las anteriores, el calculo nos introduce el término de derivada; y está describe la razón de cambio entre una variable y otra con el mismo número de elementos. Estás variables son: x (entrada), y (salida). Entonces, un cambio en los valores de x se traducirán en un cambio en los valores de y puesto que hay una correspondencia 1 a 1 entre los elementos de salida y entrada. (m =1)

Supongamos la graficación de una función líneal \(f(x) = x\) para ejemplificar lo anterior descrito: En el supuesto de la correlación entre ambas variables, sí a x le asignamos una serie de valores de -10 a 10, la variable y en concordancia, contará con los mismos. Ahora, supongase que nos ubicamos en el punto x -5 y en el punto y 5 de nuestra función; obtendríamos la coordenada: (-5,5) cuya graficación resulta en la siguiente:

Haz Clic para ver el Código

```{python}
import numpy as np
from matplotlib import pyplot as plt
import ipywidgets as widgets
from ipywidgets import interact


x = np.linspace(-10,10,100)
y = np.linspace(-10,10,100)


x1 = 5
y1= 5

x2 = -5
y2= -5 

fig = plt.figure()

plt.plot(x,y, color = 'orange', label = 'f (x) = x' )

plt.plot([x2,x1],[y2,y2], linewidth = 2,linestyle='-' ,color='darkorchid')
plt.plot([x1,x1],[y2,y1], linewidth = 2,linestyle='-' ,color='darkorchid')
plt.scatter(x1,y1, color='green', linewidth = 5, marker= '.', label= 'x')
plt.scatter(x2,y2, color='blue', linewidth = 5, marker= '.', label = 'y')
plt.legend(loc='upper left', fontsize=12)
plt.plot(legend= None)
plt.show()
```

Como puede observarse, entre ambos puntos podemos encontrar una línea recta. Esta línea recta describe la razón de cambio entre x y , de manera que la derivada corresponde a está línea recta entre el punto x (entrada) y el punto y (salida) que describe el cambio entre ambas.

Ahora considerese la graficación de la función no líneal \(f(x) = x^2\) mostrada a continuación:

Haz Clic para ver el Código

```{python}
from matplotlib import pyplot as plt
import numpy as np
import sympy as sy

from sympy import *

def f(x):
  return np.sin(x)

x = np.linspace(-np.pi,np.pi,100)

def derivate(x):
  return cos(x)

##### points
x1 = 1.57
y1 = 0.99

#####

def start_point(x1):
  y1 = f(x1)


def tangent(x, x1, y1):
    return derivate(x1)*(x - x1) + y1

limi = np.linspace(x1-1, x1+1, 10)
######################### secant 

x2,y2 = (-0.25,0.25)
x3,y3 = (-2,-0.93)

x4,y4= [-0.16,0.29]
x5, y5 = [-2, -0.93]

x6,y6= [-0.9,0.15]
x7, y7 = [-2, -0.90]

x8,y8= [-0.5,0.2]
x9, y9 = [-2, -0.90]

def slope(x2, y2, x3, y3):
  b = (y3-y2)/(x3-x2)
  return b

################
plt.figure(figsize=(8,3))

plt.plot(x,f(x), color = 'orange',label = 'sin(x)')
plt.plot(limi, tangent(limi, x1, y1), linewidth = 2, color= 'darkorchid', label = 'tangente')
plt.plot(x1,y1, color = 'darkorchid', marker= '.', markersize=14)

plt.plot([x4,x5],[f(x4),f(x5)],color='blue', label = 'secante')
plt.plot([x6,x7],[f(x6),f(x7)],color='green', label = 'secante 2')

plt.plot([x8,x9],[f(x8),f(x9)],color='red', label = 'secante 3')


plt.legend(loc='upper left', fontsize=12)


plt.plot(legend= None)
plt.show()
```

En la anterior considerese al punto x = [1.7, 0] y supongase que se quiere determinar la razón de cambio de este respecto a y. En ese punto, en la gráfica se ha marcado la recta tangente del mismo. Está “apenas” toca este punto, y está ubicada por fuera de la pendiente, en cambio si queremos determinar el cambio de la función en ese punto de x, necesitamos determinar la pendiente de la recta tangente (derivada)

Para determinar la pendiente de la recta tangente considerese la recta secante como aquella línea recta que cruza dos puntos x de la función (línea azul). Ahora, por medio de está podemos determinar la pendiente promedio entre ambos puntos, determinando el valor de la recta secante hasta que su valor se aproxime al punto x.

De manera que se requiere encontrar en primer instancia la pendiente de la recta secante por medio de dos puntos de x siguiendo la ecuación:

\[m = \frac{y_2 - y_1}{x_2 - x_1}\]

Para posteriormente encontrar la diferencia en el cambio entre ambos puntos o bien la pendiente promedio:

\[ f = \frac{x + \Delta x -f(x)}{\Delta x} \]

Hasta que el valor de \({x\Delta}\) tienda a cero, es decir el valor de \(x_2\) se acerque al de \(x_1\). Es decir, se calcula la pendiente de la recta secante y la pendiente promedio de estás hasta que el valor de \({x\Delta}\) tienda a cero. Tal cómo se muestran en las líneas verde y naranja de la gráfica, la recta secante se apróximo más al punto x respecto a la primer secante (línea azúl).

Por lo tanto, la función derivada es la recta tangente hasta el límite (la diferencia del cambio de las pendientes promedio sea cercano a 0) y está determina el cambio en cualquier punto de \(f(x)\)

\[ \frac{df}{dx} = {\lim_{x\Delta} \to 0} \frac{f(x + x\Delta) - f(x)}{x\Delta}\]

Optimización

El principio de optimización no es más que la maximización o minimización de la función de una variable. Es decir, en está se buscan los puntos críticos de una función: aquellos con mayor o menor valor, respectivamente máximo local y mínimo local. La función que es optimizada es nombrada como “función objetivo”

Un ejemplo afamado de optimización es el “Problema del Vendedor Ambulante” (Travel Salesman Problem). Este consiste en determinar la ruta más corta entre un determinado número de ciudades que el vendedor debe recorrer para ofertar sus productos. Nosotros podemos generalizar el anterior considerando al viajero como cualquier agente que busca la menor distancia para cualquier otro objetivo, como lo puede ser el rehabastecimiento de energía. En la literatura, se le conoce como problema de optimización a la elección del agente por la “mejor” solución entre las posibles, es decir, la elección por la opción que cumpla con el objetivo de maximizar o minimizar del agente en cuestión, para ello debe encontrar los parametros que logran los anteriores en una función.

Los algoritmos: Descenso de Gradiente y Ascenso de Colina son ejemplo de optimización y han sido usados para resolver diversos problemas de optimización, entre ellos, el antes mencionado el Problema del Vendedor Ambulante descrito anteriormente.

Descenso de Gradiente

El descenso de Gradiente al igual que el Ascenso de Colina descrito en el curso de ACA II 2022-I es un algoritmo de optimización. En este el objetivo del agente es llegar al valor objetivo por medio de la minimización. Considerese nuevamente la \(f(x)\). Ahora, la tarea del Descenso de Gradiente, es optimizar la variable \(x\) iterativamente o bien en la repetición de ensayos, hasta que el valor de esta se acerque al valor minimo de la derivada de \(x\) (gradiente). El cambio entre cada iteración de \(x\) es representado \({\Delta} x\), mientras \(d\) indica la diferencia y \({\alpha}\) indica el valor de cada iteración del gradiente, por lo que será nuestro parametro de escala. Lo que quiere decir, en términos coloquiales, que este define en qué medida nuestro gradiente “avanzará” en cada ensayo. Por lo que al gráficar nuestro descenso de gradiente obtendremos: (\(x_1... x_n\)), que por separado representan cada iteración quer dió el gradiente hasta cumplir con el valor objetivo de minimización.

Ahora, para el caso en el que \({\alpha} = 0\) el algoritmo no demostrará cambio alguno; en el caso en el que le asigenmos un valor bajo (cercano a 0), por ejemplo: ${} = 0.25 $ nuestro gradiente tendra iteraciones de distancia corta, por resultado, las iteraciones serán más lentas hasta llegar al objetivo, y por contrario, valores altos en \({\alpha}\) (cercanos a 1) resultarán en iteraciones con una mayor distancia y en un procesamiento más veloz. Lo anterior se resume en la siguiente ecuación: \[{\Delta} x = - {\alpha} \frac{df(x)}{dx} \]

El signo de menos en el parametro \(- {\alpha}\) cumple una función muy simple, pues este denotá la minimización de los valores de la derivada hasta llegar a un valor de cero o cercano a este. De está manera podemos dar cuenta que la estructura de la ecuación determina el comportamiento de los algoritmos de optimización; para el caso en el que el algoritmo maximice la función de descenso de gradiente, estaremos tratando con un el algoritmo de Ascenso de gradiente cuya ecuación se estructura de la siguiente:

\[{\Delta} x = {\alpha} \frac{df(x)}{dx} \] Notese que ahora se ha eliminado el signo \(-\) por lo que ahora los valores de cada iteración se maximizarán, es decir, aumentarán en cada repetición.

A continuación se te muestra una simulación del descenso de gradiente con el cual puedes interactuar eligiendo el valor de \({\alpha}\). Prueba elegir diferentes valores de \({\alpha}\); contrasta que ocurre cuándo los valores de este son muy altos (cercanos a 1) en comparación con valores bajos (cercanos a 0). ¿Qué sucede con el número de iteraciones?

Haz Clic para ver el Código

```{python}
import numpy as np
import matplotlib.pyplot as plt
import random
from numpy import linspace

r1 = 0.05
print('El valor de "alpha" para tu gradiente es: ' + str(r1))

r = float(r1)

function =  lambda x:x**2

x = np.linspace(10,-10,500)
data = 100

it_t = 100

x_x = []
y_y = []

x_start= -9.599198396793586

def derivate_x (x):
    return 2*x 

for _ in range(it_t):
    dx = -derivate_x(x_start)
    x_start +=(r*dx) 
    x_x.append(x_start)
    y_y.append(function(x_start))

b= np.linspace(-10,10,100)
c = b**2

def f(b):
    return b**2

fig, ax = plt.subplots(figsize = (8,8))
ax.spines['left'].set_position('center')
ax.spines['bottom'].set_position('zero')
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.yaxis.set_ticks_position('left')
plt.plot(legend= None)

plt.plot(b,c, color= 'orange', label = r'$f (x) = x^2$')
plt.plot(legend= None)
plt.legend(loc='upper center', fontsize=15)
plt.plot(x_x,y_y, linewidth = 2, marker = '.', markersize=14, color='darkorchid')
plt.plot(legend= None)
plt.show();
```

El valor de "alpha" para tu gradiente es: 0.05

Versión Interactiva

Aquí puedes encontrar la versión interactiva.