Convergencia absoluta de una versión subóptima del descenso más pronunciado

Question

Estoy buscando una referencia citable para rellenar un hueco en un paso intermedio de una prueba que requiere la convergencia de una versión subóptima del descenso más pronunciado.

La función $f:\bf{R}^n\to\bf{R}^n$ que estoy optimizando es estrictamente convexo y diferenciable en casi todas partes, y mis pasos de descenso más pronunciado $$x_{n+1}=x_{n}-s_k\frac{\nabla{f(x_n)}}{\|{\nabla{f(x_n)}}\|},$$ tienen tamaños de paso $s_k$ satisfaciendo $s_k\rightarrow0^+$ y $\sum_k s_k=\infty.$ Los tamaños de los pasos $s_k$ están preestablecidas, por lo que ocasionalmente puede ocurrir que un paso concreto sea contraproducente, es decir $f(x_{n+1})>f(x_n)$ .

¿Existe alguna referencia citable que afirme que $x_n$ convergerá al mínimo para casi todos los puntos de partida $x_0$ ? (La secuencia no está bien definida para todos $x$ por lo que ni siquiera está definida con certeza).

No me importa la tasa de convergencia real ni ninguna de las cuestiones de análisis numérico estándar, ya que esto es una prueba y no un cálculo.

Answer 1

Esto puede ser un poco exagerado, pero en general lo que se busca es el teorema de convergencia global de Zangwill, ver por ejemplo http://www.math.udel.edu/~angell/gl_conv.pdf

Answer 2

Supongamos que el gradiente es continuo de Lipschitz con constante $L$ (aunque no lo sepamos). Utilizando $f(y)\le f(x) + ||\nabla f(x)||^T(y-x) + \frac{L}{2}||y-x||$ y $x_{k+1}=x_k-s_k\nabla f(x)$ entonces podemos escribir $f(x_{k+1})\le f(x_k) - (1-\frac{s_kL}{2})s_k||\nabla f(x)||^2$ . Con $0<s_k\le\frac{1}{L}$ tenemos $(1-\frac{s_kL}{2})\ge \frac{1}{2}$ y por lo tanto tenemos que $f(x_{k+1})\le f(x_k) - \frac{s_k}{2}||\nabla f(x)||^2$

En el caso de tamaños de escalones decrecientes predeterminados, es decir $s_k\to 0$ entonces tenemos $s_k\in(0,\frac{1}{L}]$ para las grandes $k$ , . Por lo tanto, para un tamaño muy grande $k$ podemos entonces utilizar la idea de convergencia de Zangwill de $\sum \frac{s_k}{2}||\nabla f(x)||^2 < \infty$ (He asumido $f$ está acotado por debajo).

De alguna manera (no precisamente segura) si $\sum s_k=\infty$ entonces podemos concluir que $\underset{k\to \infty}{\text{lim}}||\nabla f(x)||\to 0$ .( http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/problemset3.pdf ). Estaré encantado si alguien puede aclarar cómo esta conclusión es válida o presentar cualquier otra prueba alternativa. Gracias.