Suponiendo que$0 \leq a_{n+1} \leq c_n a_n + b_n$ (+ otras condiciones), muestre$a_n \to 0$

Question

En el papel de "primal-dual método de división de optimización convexa ..." (ver aquí https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat-optim-JOTA-2013.pdf), Lema 4.6 indica lo siguiente:

Deje $(a_n)_n, (b_n)_n, (c_n)_n$ ser secuencias de los números reales no negativos tales que

1. $0 \leq c_n < 1$ todos los $n$,
2. $a_{n+1} \leq c_n a_n + b_n$ todos los $n$,
3. $\sum_n (1 - c_n) = \infty$,
4. $b_n / (1-c_n) \to 0$.

A continuación,$a_n \to 0$.

El papel de la cites el libro "Introducción a la Optimización" por Polyak como la fuente. Simplemente comillas "Lema de 3" de ese libro, que es en realidad Lema 3 de la Sección 2.2, página 45 (hay varios Lemas denominado "Lema 3").

Sin embargo, el libro proporciona ninguna prueba.

¿Alguien ver cómo se puede obtener? Parece ser (más o menos) bien conocido lema, por lo que también pude imaginar que hay alguna otra fuente donde esto está demostrado.

---

Como a mi propia entrada: Un par de lemas antes de la actual, se demostró mediante la consideración de un "transformado" de la secuencia (algo parecido a $(u_k - \alpha_k /(1 - q_k))_k$ viene a la mente), que luego de satisfacer de una forma más "amigable" estimación. Sin embargo, no veo que la transformación sería de gran ayuda aquí.

Answer 1

Dado $\epsilon>0$, debido a la condición 4, $N_\epsilon$ tal que para $n\ge N_\epsilon$ tenemos $b_n\le \epsilon (1-c_n)$ y por tanto, por la segunda condición $$a_{n+1}\le c_na_n+\epsilon (1-c_n)=c_n(a_n-\epsilon)+\epsilon,$$ es decir, con $\tilde a_n:=a_n-\epsilon$ hemos
$$\tilde a_{n+1}\le c_n\tilde a_n$$ para todos los $n>N_\epsilon$. Llegamos a la conclusión de que $$\tag1\limsup \tilde a_n\le \tilde a_{N_\epsilon}\cdot \lim_{M\to\infty}\prod_{n=N_\epsilon}^M c_n.$$ Si un infinidad de $c_n$$\le q<1$, el límite en el derecho claramente existe y es igual a $0$ (aquí tenemos la primera condición). Por lo tanto podemos suponer que (el uso de $c_n<1$ desde la primera condición) que todos los $c_n$ $n>N_\epsilon$ están tan cerca de $1$ que podemos aproximar $\ln c_n\approx c_n-1$ (es decir, nos encontramos con $\gamma>1$$\gamma(c_n-1)\le\ln c_n\le c_n-1$). De $$\ln\prod_{n=N}^M c_n=\sum_{n=N}^M\ln c_n\le-\gamma \sum_{n=N}^M(1-c_n)$$ vemos utilizando la condición 3 que $$\lim_{M\to\infty} \ln\prod_{n=N}^M c_n=-\infty$$, por lo tanto $$\lim_{M\to\infty} \prod_{n=N}^M c_n= 0$$ y $(1)$ hace $\limsup \tilde a_n\le 0$. Por lo $\limsup a_n\le \epsilon$ y $a_n\ge 0$ $\epsilon$ fue arbitraria, llegamos a la conclusión de $$\lim a_n= 0.$$