Tamaño de paso: 2 Número de iteraciones: 15
Métodos potenciales de prospección, FCAGLP, 2020.
MPP-2020.
Definimos la siguiente función cuadrática de $\mathbb{R}^2 \to \mathbb{R}$ a minimizar (convex minimization):
$$f(x)= \mathbf{x}^TS\mathbf{x} = \dfrac{1}{2}(x^2+by^2),$$donde observamos que las curvas de nivel de $f$ son elipses estiradas o comprimidas en la dirección $y$ por $b$. Consideramos $b>0$.
El mínimo de $f$ se encuentra en $\mathbf{x}^*=(0,0)$, donde la función toma el valor $0$. Comenzaremos la minimización partiendo de $\mathbf{x_0}=(x_0,y_0)^T=(b,1)^T$.
Nota. El número de condición (condition number) de $S$ es $1/b$. Consideremos $0<b\leq 1$. Cuando $b$ es próximo a cero, la matriz tiene un número de condición muy alto y al método se le complica arribar al argumento que minimiza a $f$. Cuando el número de condición es $1$, el problema es trivial, ya que la matriz es un múltiplo de la identidad. (De paso, vamos viendo [o recordando] que parámetros como el número de condición arroja mucha información sobre la estabilidad del algoritmo iterativo de inversión.
Valor de b: 0.1 Matriz S: [[1. 0. ] [0. 0.1]]
Consideramos un tamaño de paso $\epsilon>0$. Obtenemos por gradient descent los iterados $\mathbf{x}_k=(x_k,y_k)$,
\begin{align} x_k &= b\big(1-\epsilon\big)^k; \\ y_k &= \big(1-\epsilon b\big)^k. \end{align}Tomamos un número fijo de iteraciones para ilustrar el comportamiento del algoritmo de minimización.
Tamaño de paso: 2 Número de iteraciones: 15
Probar para $\epsilon=1,2,2.5,2/(1+b)$ y describir el comportamiento. Utilizar un número de iteraciones bajo, e.g. 15.
Observación. Apreciamos el comportamiento típico: lejos de la solución se acerca rápidamente a la "zona de confusión" (donde la norma del gradiente es pequeña); cerca de la solución (en la "zona de confusión"), oscila y puede tomar muchísimos pasos en arribar a la solución.
A modo de comentario, el método de gradientes conjugados puede conducir más rápidamente a la solución cerca del mínimo.
Ahora el método produce los iterados
\begin{align} x_k &=b\big(-\dfrac{1-b}{1+b}\big)^k; \\ y_k &=\phantom{1}\big(\dfrac{1-b}{1+b}\big)^k, \end{align}y la función vale en esos puntos $f_k=\big(\dfrac{1-b}{1+b}\big)^{2k}f(\mathbf{x_0})$. Para b<1, podemos notar como esperamos observar el zig-zag analizando el cambio de signo en $x_k$.
Nota. Para hallar el tamaño de paso exacto debemos resolver
\begin{equation} t = \text{argmin}_{s\geq 0} f(\mathbf{x}+s\mathbf{\Delta x}), \end{equation}es decir, elegir el tamaño de paso $t$ que minimiza a $f$ a lo largo del rayo $\{\mathbf{x}+t\mathbf{\Delta x} | t\geq 0 \}$. Cuando es posible, derivamos respecto de $s$ a $f(s)=f(\mathbf{x}+s\mathbf{\Delta x})$, e igualamos a cero para despejar $t$. Otras técnicas existen para proveer de valores precisos sin resolver la ecuación de forma analítica.
A modo de ejemplo, si resolvemos para hallar $t$ para k=0, tenemos $\mathbf{x}_0=(b,1)^T$, $\Delta\mathbf{x} = - \mathbf{\nabla}f(\mathbf{x}_0)=-(b,b)^T$. Calculando $f(s)$, derivando respecto a $s$ e igualando a $0$ obtenemos obtenemos $t=\frac{2}{1+b}$. Este resultado conduce a $x_1 = b\dfrac{b-1}{1+b}$, $y_1=\dfrac{1-b}{1+b}$. (Podria resolverse como ejercicio).
Observación. Al ver el gráfico de la trayectoria seguida por los $\mathbf{x}_k$ vemos que cada aproximación parte perpendicular a la linea de contorno (en la dirección opuesta al gradiente) y continua hasta que la linea es tangente a otra curva de nivel (por haber empleado exact line search). En ese punto, el método vuelve a empezar (parte perpendicular a la linea de contorno y continuará hasta que sea tangente a otra curva de nivel).
Eso es todo por hoy.