5: Optimización y Método del Gradiente Descendiente
- Page ID
- 51021
Vamos a describir el método del gradiente descente, que sirve para encontrar un punto donde la función \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) alcanza un valor mínimo.
El proceso se puede resumir en:
- Comenzamos eligiendo un valor arbitrario inicial de x.
- Buscamos la dirección v en la que \(f\) decrece más rápidamente alrededor de x. A v le llamamos dirección de máximo descenso.
-
Variamos “un poco” los valores iniciales en la dirección v:
\[\mathbf{x}\rightarrow \textbf{x}+\varepsilon\textbf{v}\] - Repetimos.
Nos detenemos ahora en el segundo paso de este proceso: cómo determinar la dirección de descenso más rápido. Como se ha visto en la sección anterior: \[f(\textbf{x}+\textbf{v}) \approx f(\textbf{x}) + \textbf{v} \nabla f(\textbf{x}) \, .\] Por la definición de producto escalar, suponiendo que v es un vector de módulo 1, la expresión anterior se escribe \[f(\textbf{x}+ \textbf{v} ) \approx f(\textbf{x}) + \textbf{v} \nabla f(\textbf{x}) = f(\textbf{x}) + \|\nabla f (\textbf{x})\|\cos(\theta) \, ,\] donde \(\theta\) es el ángulo que forman los vectores v y \(\nabla f(\textbf{x})\).
Con vistas a que \(f\) decrezca lo más rápido posible, debemos elegir \(\theta\) de forma que \(cos(\theta)\) sea lo menor posible, esto es, \(cos(\theta)= -1\).
Esto ocurre cuando \(\theta\) vale \(\pi\) (\(180^0\)) o, lo que es lo mismo, si v tiene el sintido opuesto a \(\nabla f(\textbf{x})\).
El proceso queda reescrito como:
- Comenzamos eligiendo un valor arbitrario inicial de x.
- La dirección v que hace descender más rápidamente a f alrededor de x es \(-\nabla f(\textbf{x})\). Calculamos \(\nabla f(\textbf{x})\).
-
Variamos un poco los valores iniciales en la dirección v:
\[\mathbf{x}\rightarrow \textbf{x}-\varepsilon\nabla f(\textbf{x}\] - Repetimos.
Para aplicar este algoritmo iterativo es necesario fijar dos parámetros: el número de iteraciones y el valor de \(\varepsilon\) (que se conoce como tasa de aprendizaje).
- Se dirá que el algoritmo converge si la sucesión de soluciones en el proceso iterativo se acerca a la solución óptima (esto es, el mínimo global). La cantidad de iteraciones que se necesita para que el método del gradiente descendente converja puede variar mucho (dependiendo del problema, desde unas pocas iteraciones hasta miles de ellas). En cualquier caso, la tasa de aprendizaje condicionará el número mínimo de iteraciones necesario para la convergencia.
- La tasa de aprendizaje \(\varepsilon\) es una constante, con \(0< \varepsilon < 1\), que afectará de forma significativa la efectividad del algoritmo: un valor demasiado pequeño puede llevar a que el algoritmo precise un número elevado de iteraciones antes de converger; mientras que si el valor asignado es demasiado grande, puede saltarse el mínimo global (pasando a tomar valores mayores) y no proporcionar una buena solución.