Notas para contenedor de docker:
Comando de docker para ejecución de la nota de forma local:
nota: cambiar <ruta a mi directorio> por la ruta de directorio que se desea mapear a /datos dentro del contenedor de docker.
docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0password para jupyterlab: qwerty
Detener el contenedor de docker:
docker stop jupyterlab_numericalDocumentación de la imagen de docker palmoreck/jupyterlab_numerical:1.1.0 en liga.
En esta nota se consideran resolver problemas de la forma:
$$\min f_o(x)$$con $f_o:\mathbb{R}^n \rightarrow \mathbb{R}$ fuertemente convexa y $f_o \in \mathcal{C}^2(\text{dom}f_o)$ para buscar óptimos locales. Además se asume que los puntos iniciales $x^{(0)}$ de los métodos iterativos están en $\text{dom}f_o$ y los conjuntos $f_o(x^{(0)})$-subnivel son conjuntos cerrados. Ver 1.4.Polinomios_de_Taylor_y_diferenciacion_numerica y 4.1.Optimizacion_numerica_y_machine_learning para definiciones utilizadas en esta nota.
También se asume que existe un punto óptimo $x^*$ por lo que el problema tiene solución y el valor óptimo se denota por $p^* = f_o(x^*) = \inf f_o(x)$
Las suposición que una función $f$ sea convexa asegura que una condición necesaria y suficiente para que $x^*$ sea óptimo es: $\nabla f(x^*) = 0$. Así, tenemos que resolver $\nabla f(x)=0$ la cual es en general es un conjunto de $n$ ecuaciones no lineales en $n$ variables y que resuelve el problema de optimización planteado al inicio.
Ejemplos:
1)$$\displaystyle \min_{x \in \mathbb{R}^2} x_1^4+2x_1^2x_2+x_2^2$$
Entonces:
$$ \nabla f_o(x) = \left [ \begin{array}{c} 4x_1^3+4x_1x_2\\ 2x_1^2+2x_2 \end{array} \right ]=0 $$que es una ecuación de dos variables y dos incógnitas no lineal.
2) $$\displaystyle \min_{x \in \mathbb{R}^2} \frac{1}{2}x^TPx+q^Tx+r$$
con $P=\left [\begin{array}{cc} 5 & 4\\ 4 & 5 \end{array} \right ]$, $q=\left [\begin{array}{c} -1\\ 1 \end{array} \right] $, $r=3$. Obsérvese que haciendo las multiplicaciones de matriz-vector y productos punto se reescribe el problema como:
Entonces:
$$\nabla f_o(x) = Px +q =\left [ \begin{array}{cc} 5 & 4\\ 4 & 5 \end{array} \right ] \left [ \begin{array}{c} x_1\\ x_2 \end{array} \right ] + \left [ \begin{array}{c} -1\\ 1 \end{array} \right ]= \left [ \begin{array}{cc} 5x_1+4x_2-1\\ 4x_1+5x_2+1 \end{array} \right ] =0 $$que es una ecuación en dos variables con dos incógnitas lineal.
Comentario: en algunos casos especiales es posible resolver la ecuación no lineal $\nabla f_o(x) = 0$ para $x$ de forma analítica o cerrada. Este es el caso del ejemplo $2$ anterior la cual está dada por $x^* = -P^{-1}q$:
In [1]:
import numpy as np
In [2]:
P=np.array([[5,4],[4,5]])
q=np.array([-1,1])
np.linalg.solve(P,-q)
Out[2]:
pero típicamente se utiliza un método iterativo: calcular una secuencia de puntos $x^{(0)}, x^{(1)}, \dots \in \text{dom}f_o$ con $f_o(x^{(k)}) \rightarrow p^*$ si $k \rightarrow \infty$. El conjunto de puntos $x^{(0)}, x^{(1)},\dots$ se nombra secuencia de minimización para el problema de optimización. El algoritmo termina si $f_o(x^{(k)})-p^* \leq \epsilon$ con $\epsilon >0$ una tolerancia dada. Tales métodos se conocen con el nombre de métodos de descenso.
La secuencia de minimización se obtiene con la fórmula: $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$. Al vector $\Delta x \in \mathbb{R}^n$ se le nombra paso o dirección de búsqueda. Al escalar $t^{(k)}$ se le nombra tamaño o longitud de paso y siempre es positivo salvo en el caso en que $x^{(k)}$ sea óptimo.
Se les nombra métodos de descenso pues para la secuencia de minimización se cumple la desigualdad: $f_o(x^{(k+1)}) < f_o(x^{(k)})$, excepto para $x^{(k)}$ óptimo.
La suposición que el conjunto $f_o(x^{(0)})$-subnivel sea cerrado garantiza que la secuencia de minimización está en el conjunto $f_o(x^{(0)})$-subnivel para todas las iteraciones.
Condición para que un paso o dirección de búsqueda sea de descenso
Si el paso o dirección de búsqueda satisface la condición: $\nabla f_o^T(x^{(k)})\Delta x^{(k)} < 0$ se le nombra dirección de descenso. Geométricamente las direcciones de descenso forman un ángulo agudo con $-\nabla f_o(x^{(k)})$:
Algoritmo general de descenso
Dado un punto inicial $x$ en $\text{dom}f_o$
Repetir el siguiente bloque para $k=0,1,2,...$
- Determinar una dirección de descenso $\Delta x$.
- Búsqueda de línea. Elegir un tamaño de paso $t > 0$.
- Hacer la actualización: $x = x + t\Delta x$.
hasta convergencia (satisfacer criterio de paro).
Nota: los pasos en el algoritmo anterior representan una guía para la implementación. Al describirse los pasos de un algoritmo no implica que se tengan que implementar uno a continuación del otro como se describe. Si una implementación respeta la lógica y al mismo método, entonces pueden seguirse los pasos de una forma distinta.
Comentarios:
El método de descenso en gradiente utiliza $\Delta x = - \nabla f_o(x)$. Ver 4.1.Optimizacion_numerica_y_machine_learning.
El criterio de paro típicamente es de la forma $||\nabla f_o(x)|| \leq \text{TOL}$ donde: $\text{TOL}$ es una cantidad pequeña y positiva (menor o igual a $10^{-8}$). También se involucra el número máximo de iteraciones en el criterio de paro.
El paso $2$ busca reducir $f_o$ lo suficiente o minimizarla aproximadamente a lo largo de un rayo*. Uno de los métodos que permite de forma sencilla lo anterior es la búsqueda de línea por backtracking.
* Un rayo es el conjunto definido por $\{x + \theta v : \theta \geq 0 , v \neq 0, v \in \mathbb{R}^n\}$ para $x \in \mathbb{R}^n$.
Para entender el método de búsqueda de línea por backtracking supóngase que $f_o$ tiene una forma siguiente:
Y considérese una función $g: \mathbb{R} \rightarrow \mathbb{R}$ igual a $f_o$ pero restringida al rayo $x + t\Delta x$, esto es: $g(t) = f_o(x+t \Delta x)$ con $t>0$, $\Delta x$ dirección de descenso. Lo anterior se visualiza como sigue:
Y como $f_o$ es continua y diferenciable, $g$ también lo es y $g(0)=f_o(x)$, $g'(t) = \nabla f_o(x+t\Delta x)^T \Delta x$. Si graficamos $g$ se tendría:
En la búsqueda de línea se construyen dos rectas. Una recta es $g(0) + \alpha g'(0)(t-0)$ con $\alpha \in (0,\frac{1}{2})$. La otra recta es $g(0)+g'(0)(t-0)$. Ambas rectas tienen pendiente negativa. Esto se visualiza como sigue:
En la búsqueda de línea por backtracking se busca $t_k$ tal que $f_o$ decrezca suficientemente. Lo anterior se establece con la desigualdad $f_o(x+t \Delta x) < f_o(x) + \alpha t \nabla f_o(x)^T \Delta x$:
obsérvese en el dibujo anterior que la región en la que se elegirá $t_k$ está a la izquierda de la línea punteada vertical de color verde.
Y visualmente en $R^3$ se tiene:
El método depende de dos constantes $\alpha$ y $\beta$ con $\alpha \in (0,\frac{1}{2})$ y $\beta \in (0,1)$.
Algoritmo de búsqueda de línea por backtracking
Dados $\Delta x$ dirección de descenso para $f_o$ en $x \in \text{dom}f_o$, $\alpha \in (0,\frac{1}{2})$, $\beta \in (0,1)$.
Asignar t=1.
Mientras $f_o(x+t\Delta x) > f_o(x) + \alpha t \nabla f_o(x) ^T\Delta x$.
- Reducir $t: t= \beta t$.
Comentarios:
El valor $\alpha$ típicamente se elige entre $.01$ y $.03$ que indica que se acepta un decrecimiento en el valor de $f_o$ entre el $1 \%$ y el $30 \%$. La constante $\beta$ comúnmente se elige entre $.1$ (que modifica fuertemente $t$) y $.8$ (que realiza una modificación menos drástica de $t$).
Obsérvese que la multiplicación $\nabla f_o(x)^T \Delta x$ es una derivada direccional, ver 1.4.Polinomios_de_Taylor_y_diferenciacion_numerica.
Primero se busca una dirección $\Delta x_{\text{nsd}}$ que satisfaga: $$\Delta x_{\text{nsd}} = \text{argmin} \{ \nabla f_o(x)^Tv : ||v|| \leq 1, \nabla f_o(x)^Tv < 0 \} $$ donde: $|| \cdot||$ es alguna norma en $\mathbb{R}^n$.
Posteriormente con $\Delta x_{\text{nsd}}$ se define el paso $\Delta x_{\text{sd}}=||\nabla f_o(x)||_* \Delta x_{\text{nsd}}$ donde: $|| \cdot||_*$ es la norma dual*.
*La norma dual asociada a $||\cdot||$ se denota como $||\cdot||_*$ y se define como: $||z||_* = \sup \{z^Tx :||x||= 1\}$. Para los casos que veremos es suficiente saber que $||z||_{2*}$ (la norma dual de la norma $2$) es $||z||_2$ y $||z||_{1*}$ (la norma dual de la norma $1$) es $||z||_\infty$ $\forall z \in \mathbb{R}^n$.
Comentarios:
$\Delta x_{\text{sd}}$ es dirección de descenso.
Por la definición de $\Delta x_{\text{nsd}}$ anterior, se puede elegir alguna norma vectorial $||\cdot||$:
Si $||\cdot||$ es la norma $2$: $\Delta x_{\text{nsd}} = \text{argmin} \{ \nabla f_o(x)^Tv : ||v||_2 \leq 1, \nabla f_o(x)^Tv < 0 \} $ entonces $\Delta x_{\text{sd}} = - \nabla f_o(x)$. Con esto se prueba que el método de steepest descent generaliza al método de descenso en gradiente.
Si $||\cdot||$ es una norma cuadrática* con matriz $P$: $\Delta x_{\text{nsd}} = \text{argmin} \{ \nabla f_o(x)^Tv : ||v||_P \leq 1, \nabla f_o(x)^Tv < 0 \} $ se prueba que $\Delta x_{\text{sd}} = - P^{-1} \nabla f_o(x)$.
Si $||\cdot||$ es la norma $1$: $\Delta x_{\text{nsd}} = \text{argmin} \{ \nabla f_o(x)^Tv : ||v||_1 \leq 1, \nabla f_o(x)^Tv < 0 \} $ se prueba que $\Delta x_{\text{sd}} = - \frac{\partial f(x)}{\partial x_i} e_i$ con $e_i$ $i$-ésimo vector canónico y el índice $i$ es la entrada del vector $\nabla f_o(x)$ de máxima magnitud: $i$ tal que $\left |(\nabla f_o(x))_i \right | = ||\nabla f_o(x)||_\infty$. En este caso el método se nombra descenso por coordenadas o coordinate descent. En cada iteración una única componente de $x$ es actualizada.
*La norma cuadrática de $z$ con matriz $P$ se define como $||z||_P = \sqrt{z^TPz}$ con $P$ matriz simétrica definida positiva
*Recuérdese que la aproximación lineal de una función $f$ está dada por Taylor a primer orden: $f(x+v)=\hat{f}(x+v) = f(x) + \nabla f(x)^Tv$.
Con la norma cuadrática:
Con la norma 1:
Algoritmo de descenso más pronunciado
Dado un punto inicial $x$ en $\text{dom}f_o$
Repetir el siguiente bloque para $k=0,1,2,...$
- Calcular la dirección de descenso más pronunciada $\Delta x_{\text{sd}}$.
- Búsqueda de línea. Elegir un tamaño de paso $t > 0$.
- Hacer la actualización: $x = x + t\Delta x_{\text{sd}}$.
hasta convergencia (satisfacer criterio de paro).
Nota: los pasos en el algoritmo anterior representan una guía para la implementación. Al describirse los pasos de un algoritmo no implica que se tengan que implementar uno a continuación del otro como se describe. Si una implementación respeta la lógica y al mismo método, entonces pueden seguirse los pasos de una forma distinta.
En esta sección consideramos una norma cuadrática: $||z||_P = \sqrt{z^TPz}$ con $P$ matriz simétrica definida positiva para el método de descenso más pronunciado. Bajo esta norma se cumple: $\Delta x_{\text{sd}} = -P^{-1}\nabla f_o(x)$.
Comentarios:
Obsérvese que el método de descenso más pronunciado generaliza al método de descenso en gradiente con $P=I$ la matriz identidad.
Es posible probar que el método de descenso más pronunciado bajo la norma cuadrática $||\cdot||_P$ es el método de descenso en gradiente aplicado al problema de optimización después del cambio de coordenadas $\hat{x}=P^{1/2}x$. En este cambio de coordenadas $x$ es la variable original por lo que si deseamos utilizar descenso en gradiente utilizamos la inversa de la matriz raíz cuadrada simétrica* $P^{1/2}$ quedando la transformación como: $x = P^{-1/2}\hat{x}$.
*$P^{1/2}$ se nombra raíz cuadrada simétrica o symmetric squareroot y está definida para matrices $P$ simétricas semidefinidas positivas como $P^{1/2}=Qdiag(\lambda_1^{1/2},\dots,\lambda_n^{1/2})Q^T$ con $Q$ y $diag(\lambda_1^{1/2},\dots,\lambda_n^{1/2})$ obtenidas con la descomposición espectral de $P$, ver 3.3.d.SVD.
Referencias: