¿Cómo se elige el tamaño del escalón para el descenso más pronunciado?

Question

Consideremos la búsqueda del valor mínimo de cualquier función $g$ de $\mathbb{R}^n$ a $\mathbb{R}$ . El método del descenso más pronunciado para encontrar un mínimo local de una función arbitraria $g$ de de $\mathbb{R}^n$ a $\mathbb{R}$ puede describirse intuitivamente del siguiente modo:

1. Evalúe $g$ en una primera aproximación $x^{(0)} = (x^{(0)}_{1}, ..., x^{(0)}_{D})^t$
2. Determinar una dirección de $x^{(0)}$ que se traduce en una disminución del valor de $g$ (o la mayor disminución utilizando $\bigtriangledown g(x)$ el gradiente de $g$ como en el descenso gradiente)
3. Mueve una cantidad apropiada en esta dirección y llama al nuevo valor $x^{(1)}$ .
4. Repita los pasos 1 a 3 con $x^{(0)}$ sustituido por $x^{(1)}$ .

Por lo general, el paso 3 se ejecuta de la siguiente manera (ya que el objetivo es reducir $g(x)$ a su valor minial):

$$x^{(1)} = x^{(0)} - \alpha \bigtriangledown g(x^{(0)} )$$

para alguna constante $\alpha > 0$ .

Sin embargo, para nosotros esa ecuación de descenso hay que elegir un valor apropiado de $\alpha$ para que $g(x^{(1)} )$ es menor que $g(x^{(0)} )$ . Según el libro de texto de análisis numérico de Burden y Faires para determinar una elección apropiada para el valor de $\alpha$ consideramos la función de una sola variable:

$$h(\alpha) = g(x^{(0)} - \alpha \bigtriangledown g( x^{(0)} )$$

Según ellos, el valor de $\alpha$ que minimiza $h$ es el valor necesario para la ecuación de descenso de gradiente.

Lo que no entiendo es;

1. por qué el valor óptimo de $\alpha$ ? ( es decir, la solución a la minimización de $h( \alpha )$ ?)
2. ¿Qué significa el valor "óptimo" de alfa en este caso y por qué minimizar $h( \alpha)$ captar esta definición de optimalidad? ¿Quizás es la elección de alfa que da el mayor tamaño de paso posible dado el gradiente calculado?
3. ¿Qué es el prueba o el justificación rigurosa que esta ecuación es la que hay que optimizar para elegir el tamaño del paso? ¿Por qué es esa la ecuación correcta y no otra? ¿Existe un por qué riguroso que explique por qué ¿ese es el mejor alfa?
4. ¿Qué tipo de garantías ofrece esa elección de $\alpha$ nos dan? Si elegimos que $alpha$ ¿tenemos la garantía de que si seguimos haciendo iteraciones del descenso más pronunciado, nunca nos sobrepasaremos? ¿Será en un número infinito de iteraciones o en iteraciones finitas?
5. ¿Significa esto que elegimos un nuevo tamaño de paso para cada paso del descenso más pronunciado?

Answer 1

Obsérvese que, por definición

$$h(\alpha) \equiv g\left(x^{(0)} - \alpha \nabla g\left( x^{(0)} \right)\right) = g\left( x^{(1)} \right).$$

Dado que el objetivo es elegir el paso con el descenso más profundo, esto puede lograrse eligiendo $\alpha$ para minimizar $h(\alpha)$ . Esto equivale a resolver

$$\min_\alpha g\left( x^{(1)} \right),\;\;\;\text{ subject to}\;\; x^{(1)}=x^{(0)} - \alpha \nabla g\left( x^{(0)} \right).$$

Answer 2

Obsérvese que el objetivo es llegar a algún mínimo de $g(x)$ . es decir, queremos:

$$\min_{x \in R^n} g(x)$$

tenga en cuenta que $x$ puede ser un vector multivariable.

Puesto que no tenemos una forma mejor de alcanzar un mínimo, sigamos la dirección del mayor cambio hacia algún mínimo. Esta es la regla de actualización:

$$x^{(1)} := x^{(0)} - \alpha \nabla g(x^{(0)})$$

Sin embargo, ahora nos queda elegir un buen tamaño de escalón $\alpha$ . Desafortunadamente, en cualquier punto de este algoritmo sólo hay dos cosas que sabemos, nuestra conjetura actual $g(x^{(0)})$ y la dirección de mayor cambio $\nabla g(x^{(0)})$ . Si pudiéramos, querríamos elegir $x^{(1)}$ tal que corresponda a un mínimo, es decir, que sería bueno tener:

$$\min_{x \in R^n} g(x) = \min_{x^{(1)} \in X^{(1)} } g(x^{(1)})$$

donde $X^{(1)}$ denota el conjunto de candidatos $x^{(1)}$ que podríamos elegir (basándonos en las dos cosas que sabemos). Sería impresionante si pudiéramos llegar al mínimo así porque significa que elegimos un nuevo $x^{(1)}$ tal que se encuentre en el mínimo (local) que buscamos. Por desgracia, estamos limitados a la estimación anterior ( $x^{(0)}$ ) que teníamos. Así que en realidad, tenemos:

$$\min_{x^{(1)} \in X^{(1)} } g(x^{(1)}) \iff \min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

Así pues, ¡estos dos problemas de optimización son equivalentes!

En este punto, el aspecto clave a tener en cuenta es que nuestro problema original es $\min_{x \in R^n} g(x)$ y lo sustituimos eligiendo un vector multivariable en un conjunto restringido. ¿Cómo está restringido? Sólo podemos elegir $x^{(1)}$ basado en el gradiente y nuestra estimación anterior. Así que tiene sentido elegir $\alpha$ (y por tanto $x^{(1)}$ de forma que minimicemos $g(x)$ en la medida de lo posible. De todas formas, ¡ese era nuestro objetivo desde el principio! Nuestro objetivo es elegir el $g(x)$ por lo que en cada paso, nos aseguramos de elegir un $\alpha$ de forma que minimicemos nuestro objetivo original $g(x)$ en la medida de lo posible.

---

Abordemos los puntos de la pregunta original:

1. La razón por la que $min_{\alpha} h(\alpha)$ es el valor óptimo de $\alpha$ es porque, estamos eligiendo el tamaño de paso que nos asegura minimizar nuestro objetivo $g(x)$ tanto como sea posible, dado que sólo conocemos nuestra estimación previa del mínimo y la dirección del mayor cambio. Así que elegimos un alfa tal que $min g(x^{(1)})$ se cumple.
2. La optimalidad en este caso significa que elegimos un tamaño de paso tal que disminuyamos nuestra función tanto como sea posible (dada la información que tenemos, es decir, sólo conocemos su estimación anterior y la dirección del cambio más pronunciado).
3. La justificación es que, dadas las restricciones del problema, no podemos hacer nada mejor que elegir el siguiente $x^{(1)}$ lo más cerca de nuestro objetivo real $min g(x)$ como sea posible.
4. Si observa $\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$ tiene la misma forma que nuestro objetivo real $min g(x)$ . Por lo tanto, una solución para $\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$ sólo tratará de minimizar la función objetivo original $g$ sujeto a las restricciones. La propiedad realmente buena de esto es que si la solución óptima $x^*$ está siempre en el conjunto restringido $X^{(1)}$ se elegirá la solución. Observe también que estamos eligiendo un nuevo tamaño de paso basado en nuestra estimación anterior. Así que sólo vamos a elegir un tamaño de paso que minimiza nuestra conjetura actual....¿por qué? Porque así es como planteamos el problema, mira:

$$\min_{\alpha \in R } g(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

Elegir un tamaño de paso sólo si mejora nuestra solución actual, es una forma de reformularlo. Así que es clave que en este segundo problema de optimización que elegimos la misma función objetivo para optimizar sobre $x^{(1)}$ . Si elegimos algún otro $g'$ tendríamos:

$$\min_{\alpha \in R } g'(x^{(1)}), \text{ subject to } x^{(0)} - \alpha \nabla g(x^{(0)})$$

lo que no mejora necesariamente nuestro objetivo real de minimizar $g$ .

5. Sí, es necesario elegir un nuevo tamaño de paso y resolver el problema de optimización en cada paso del algoritmo.

---

Nunca lo he dicho explícitamente, pero:

$$X^{(1)} = \{ x^{(1)} \in R^n \mid x^{(0)} - \alpha \nabla g(x^{(0)}), \alpha \in R \}$$

por lo que sólo estamos considerando puntos en el hiperplano descrito por el vector $\nabla g(x^{(0)})$ y el punto para "alcanzar" el plano $x^{(0)}$ .

Answer 3

No creo que todas las preguntas estén formuladas del todo correctamente:

1. El libro de texto no dice que la elección de $\alpha$ es óptimo sólo lo encuentran apropiado . Es óptimo para el primer paso porque minimiza $g(x^{(1)})$ por diseño, pero no hay razón para que sea óptimo en los pasos siguientes. De hecho, se puede encontrar un ejemplo con un descenso de gradiente divergente teniendo $\alpha$ establecidos según Burden y Fairs.
2. Un óptimo $\alpha$ sería aquella que garantizara la conversión con el mínimo número de pasos.
3. Según la definición de $h(\alpha)$ sabemos que $$\min_{\alpha}h(\alpha) = \min_{x\in X^{(1)}}g(x),$$ $$X^{(1)} = \{ g(x^{(0)}) - \alpha \nabla g(x^{(0)})\}$$ Tenga en cuenta que $X^{(1)}$ es el conjunto de todos los valores posibles para $x^{(1)}$ . Por lo tanto, si encontramos un $\alpha$ que minimiza $h(\alpha)$ También hemos encontrado un $x \in X^{(1)}$ que minimice $g(x)$ utilizando ese $\alpha$ es decir, nuestro $\alpha$ es la mejor opción para encontrar $x^{(1)}$ tal y como lo define el descenso por gradiente.
4. Esta elección de $\alpha$ garantiza que el primera iteración nos da la mejor solución posible.
5. No, esto sería completamente impracticable. Incluso es poco práctico elegir un $\alpha$ minimizando realmente $h(\alpha)$ en primer lugar. Sólo expresa una idea simple: Tomemos un $\alpha$ que minimice nuestra función objetivo óptima en el primer paso. Pero esto conduce a otro problema de minimización. Así, para una dimensión $g(x)$ por ejemplo, conocer un $\alpha$ es tan bueno como conocer un $x$ que minimiza $g(x)$ .