5

In the paper "A primal-dual splitting method for convex optimization ..." (see here https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat-optim-JOTA-2013.pdf), Lemma 4.6 states the following:

Let $(a_n)_n, (b_n)_n, (c_n)_n$ be sequences of nonnegative real numbers such that

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

Then $a_n \to 0$.

The paper cites the book "Introduction to Optimization" by Polyak as the source. It just quotes "Lemma 3" from that book, which is actually Lemma 3 of Section 2.2, page 45 (there are multiple Lemmas named "Lemma 3").

Nevertheless, the book provides no proof.

Does anyone see how this can be obtained? It seems to be a (more or less) well-known lemma, so I could also imagine that there is some other source where this is proved.

As to my own input: A few lemmas before the current one are proved by considering a "transformed" sequence (something like $(u_k - \alpha_k /(1 - q_k))_k$ comes to mind) which then satisfy a more "friendly" estimate. However, I don't see which transformation would be helpful here.
PhoemueX
  • 35,087

1 Answers1

4

Given $\epsilon>0$, because of condition 4, there is $N_\epsilon$ such that for $n\ge N_\epsilon$ we have $b_n\le \epsilon (1-c_n)$ and so by the second condition $$a_{n+1}\le c_na_n+\epsilon (1-c_n)=c_n(a_n-\epsilon)+\epsilon,$$ i.e., with $\tilde a_n:=a_n-\epsilon$ we have
$$\tilde a_{n+1}\le c_n\tilde a_n$$ for all $n>N_\epsilon$. We conclude that $$\tag1\limsup \tilde a_n\le \tilde a_{N_\epsilon}\cdot \lim_{M\to\infty}\prod_{n=N_\epsilon}^M c_n.$$ If infinitely many $c_n$ are $\le q<1$, the limit on the right clearly exists and equals $0$ (here we the first condition). Hence we may assume (using $c_n<1$ from the first condition) that all $c_n$ with $n>N_\epsilon$ are so close to $1$ that we can approximate $\ln c_n\approx c_n-1$ (i.e., we find $\gamma>1$ with $\gamma(c_n-1)\le\ln c_n\le c_n-1$). From $$\ln\prod_{n=N}^M c_n=\sum_{n=N}^M\ln c_n\le-\gamma \sum_{n=N}^M(1-c_n)$$ we see uisng condition 3 that $$\lim_{M\to\infty} \ln\prod_{n=N}^M c_n=-\infty$$, hence $$\lim_{M\to\infty} \prod_{n=N}^M c_n= 0$$ and $(1)$ becomes $\limsup \tilde a_n\le 0$. So $\limsup a_n\le \epsilon$ and as $a_n\ge 0$ and $\epsilon$ was arbitrary, we conclude $$\lim a_n= 0.$$

Hagen von Eitzen
  • 374,180