Estoy leyendo los apuntes de Daniel Spielman sobre el método de Descenso de Gradiente Conjugado (Enlace a las notas de la conferencia) y en él demuestra que el tamaño de paso óptimo para $\alpha$ viene dada por $$ \frac{2}{\lambda_1 + \lambda_n}.$$ No entiendo cómo se deriva esto. En detalle: Dejemos que $0 < \lambda_1 \leq \ldots \leq \lambda_n$ sean los valores propios de la matriz psd $A$ . Entonces, el tamaño del paso $\alpha$ viene dado por el mínimo con respecto a $\alpha$ de $$\max_i | 1- \alpha \lambda_i| = |\max(1-\alpha \lambda_1, 1- \alpha \lambda_n) |.$$ Me preguntaba cómo puedo calcular esta solución.
Respuesta
¿Demasiados anuncios?
Tenga en cuenta que para minimizar $\max\limits_{i}\left|1-\alpha\lambda_i\right|$ con respecto a $\alpha$ queremos los valores extremos que lo limitan, es decir $\left|1-\alpha\lambda_1\right|$ y $\left|1-\alpha\lambda_n\right|$ para que sean iguales.
Por lo tanto, se establece $\left|1-\alpha\lambda_1\right| = \left|1-\alpha\lambda_n\right|$ . Recordemos que $\alpha > 0$ y $\lambda_1 < \lambda_n$ . Dadas estas restricciones, la única forma de obtener la igualdad es cuando $1 - \alpha\lambda_n < 0$ y $1-\alpha\lambda_1 > 0$ y viceversa. Así, tenemos
$$ 1-\alpha\lambda_1 = -(1-\alpha\lambda_n) \implies \alpha = \frac{2}{\lambda_1 + \lambda_n} $$
