[Masacroso]

Pero no me queda claro, entonces, cómo partiendo de que \( x_m \) converge y de que el gradiente del límite \( \nabla (\lim f(x_m)) = 0 \), ¿cómo pruebo que \( x_m \) converge a \( u \)?

Es decir, yo trato de obtener que \(x_m\rightarrow u\), no que \(u\) es punto crítico.

Sinceramente, no entiendo bien qué duda tienes. Si \( \{x_n\}_{n\in\mathbb{N}} \) converge ya está, ya sabes que converge a un punto que es punto crítico. A ese punto lo podemos llamar \( u \), \( x \) o como te plazca.

Ahora bien, si llamamos al punto de convergencia \( u \), te queda probar que \( u \) es un mínimo absoluto de la función. Para ello basta estudiar la función y ver que

1) tiene un único punto crítico y
2) tal punto crítico corresponde a un mínimo absoluto.

El 1) se sigue fácilmente de la ecuación \( \nabla f(x)=0 \) y el hecho de que \( A^\top A \) es invertible, y 2) de que \( f \) es estrictamente convexa.

[Luis Fuentes]

Hola

Pero no me queda claro, entonces, cómo partiendo de que \( x_m \) converge y de que el gradiente del límite \( \nabla (\lim f(x_m)) = 0 \), ¿cómo pruebo que \( x_m \) converge a \( u \)?

¡Te escribí en un mensaje previo la demostración!

El gradiente explícitamente es:

\( \nabla f(x_m)=2A^tAx_m-2A^tb \)

Si pruebas que converge a cero tienes que:

\( A^tAx_m\to A^tb \)

y dado que \( A^tA \) es inversible:

\( x_m\to (A^tA)^{-1}A^tb \)

Ahí se demuestra que \( x_m\to (A^tA)^{-1}A^tb=u \); algebraicamente se puede ver que esa es la expresión del mínimo o, ahora si, una vez que sabemos que \( x_m \) converge, terminar como tu habías hecho (con la escritura propuesta por Masacroso).

Saludos.

[Daxito]

Una duda en la que me acabo de fijar, cuando haces \( g(x_{n+1})-g(x_n) \) y pasas de la primera desigualdad a la segunda y divides por \( -\alpha/2 \), no cambiaria también el símbolo de menor igual a mayor igual?

Claro, aquí tienes mi desarrollo de los dos primeros apartados:

Sea \( \alpha = \frac{1}{2 \|A^t A\|_2} \), fijamos \( x_0 \in \mathbb{R}^n \). Definimos \( x_{n+1} = x_n - \alpha \nabla g(x_n) = x_n - \frac{1}{2 \|A^t A\|_2} \nabla g(x_n) \).

Sea el desarrollo de Taylor de orden dos de \( g \) en \( x_n \):

\[ g(x) = g(x_n) + \nabla g(x_n)^t (x - x_n) + \frac{1}{2} (x - x_n)^t \nabla^2 g(x_n) (x - x_n) + \Theta(\|x - x_n\|^3) \]

Ya que \( g \) es una función cuadrática (no tiene términos de orden mayor a dos)

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (x_{n+1} - x_n) + \frac{1}{2} (x_{n+1} - x_n)^t \nabla^2 g(x_n) (x_{n+1} - x_n). \)

Sustituyendo \( x_{n+1} = x_n - \alpha \nabla g(x_n) \):

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (-\alpha \nabla g(x_n)) + \frac{1}{2} (-\alpha \nabla g(x_n))^t \nabla^2 g(x_n) (-\alpha \nabla g(x_n)). \)

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n). \]

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \|\nabla g(x_n)\|_2^2. \]

Veamos ahora si la siguiente desigualdad es cierta:

\[ g(x_{n+1}) - g(x_n) = -\alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \|\nabla g(x_n)\|_2^2 \leq -\frac{\alpha}{2} \|\nabla g(x_n)\|_2^2 \Leftrightarrow \]

\[ \Leftrightarrow 2 \|\nabla g(x_n)\|_2^2 -\alpha \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n) \leq \|\nabla g(x_n)\|_2^2 \Leftrightarrow \]

\[ \Leftrightarrow \|\nabla g(x_n)\|_2^2 \leq \alpha \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n) \]

Sea \( c \) el término de la izquierda y \( d \) el de la derecha

\[ c = \|2A^t (Ax - b)\|_2^2 = (2A^t (Ax - b))^t (2A^t (Ax - b)) = 4(Ax - b)^t A^t A (Ax - b), \]

\[ \alpha d = \alpha (2A^t (Ax - b))^t (2A^tA)^2 (2A^t (Ax - b)) = \alpha 16(Ax - b)^t A^t A A^t A(Ax - b) \]
\[ \quad\;\, \leq \alpha 16 \|A^t A\|_2 (Ax - b)^t A^t A (Ax - b) \]

Dividiendo ambos lados por \( 4(Ax - b)^t A^t A (Ax - b) \), se concluye que:

\[ 1 < \alpha \cdot 4 \|A^t A\|_2 \Leftrightarrow 1 < \alpha \frac{1}{2 \|A^t A\|_2} = 2 \]

Para el apartado dos:

Como la sucesión \( g(x_n) \) es estrictamente decreciente y acotada inferiormente por \( g(u) \) (al ser \( g(u) \) mínimo absoluto), esto asegura que \( g(x_n) \) converge a un valor \( L \) con \( L \geq g(u) \). La última desigualdad de \( \alpha d \) se cumple porque \( AA^t \) es simétrica y definida positiva y por tanto \( v^tAA^tv = \|A^t A\|_2 \|v\|_2 \).

Mensaje de la moderación: se ha corregido el \( \LaTeX \) para que las frases tengan ancho adaptable y sean fáciles de leer desde cualquier dispositivo. En la medida de lo posible evita el uso del entorno \text{... }, especialmente para escribir frases.

[Luis Fuentes]

Hola

 No tengo mucho tiempo ahora pero...

Una duda en la que me acabo de fijar, cuando haces \( g(x_{n+1})-g(x_n) \) y pasas de la primera desigualdad a la segunda y divides por \( -\alpha/2 \), no cambiaria también el símbolo de menor igual a mayor igual?

Antes de nada. El desarrollo sobre el cuál preguntas lo habías puesto tu. ¿Te estas preguntando una duda a ti mismo?. 

Sea como sea es un poco batiburrillo; tiene varios errores o cosas mal explicadas. Desde luego en ningún sitio de divide por \( -\alpha/2 \).

Pero antes de eso:

Claro, aquí tienes mi desarrollo de los dos primeros apartados:

Sea \( \alpha = \frac{1}{2 \|A^t A\|_2} \), fijamos \( x_0 \in \mathbb{R}^n \). Definimos \( x_{n+1} = x_n - \alpha \nabla g(x_n) = x_n - \frac{1}{2 \|A^t A\|_2} \nabla g(x_n) \).

Sea el desarrollo de Taylor de orden dos de \( g \) en \( x_n \):

\[ g(x) = g(x_n) + \nabla g(x_n)^t (x - x_n) + \frac{1}{2} (x - x_n)^t \nabla^2 g(x_n) (x - x_n) + \Theta(\|x - x_n\|^3) \]

Ya que \( g \) es una función cuadrática (no tiene términos de orden mayor a dos)

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (x_{n+1} - x_n) + \frac{1}{2} (x_{n+1} - x_n)^t \nabla^2 g(x_n) (x_{n+1} - x_n). \)

Sustituyendo \( x_{n+1} = x_n - \alpha \nabla g(x_n) \):

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (-\alpha \nabla g(x_n)) + \frac{1}{2} (-\alpha \nabla g(x_n))^t \nabla^2 g(x_n) (-\alpha \nabla g(x_n)). \)

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n). \]

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \|\nabla g(x_n)\|_2^2. \]

Esa última igualdad, en principio, no se sabe de donde sale. No se deduce directamente de la anterior. A partir de ahí me cuesta seguir exactamente qué hace; desde luego como mínimo hay erratas que dificultan la comprensión.

Cuando tenga un rato lo miro más despacio.

Saludos.