# Convergence of a sequence by iteration

Let $F:\mathbb R^d\to\mathbb R$ be a convex function. Assume that $F$ has a uniformly bounded gradient, $|\sup_{x\in\mathbb R^d}\nabla F(x)|<+\infty$. Define the sequence as follows: Take an arbitrary $x_0\in\mathbb R^d$ and set $x_{n+1}:=\nabla F(x_n)$ for $n\ge 0$.

I am very interested in the convergence of $(x_n)_{n\ge 1}$. First this sequence is bounded by definition. Second, it follows from definition that

$$(x_{n+1}-x_n)\cdot (x_n-x_{n-1}) \quad =\quad \big(\nabla F(x_n)-\nabla F(x_{n-1})\big)\cdot (x_n-x_{n-1}) \ge 0.$$

If $d=1$, then $(x_n)_{n\ge 1}$ is monotone and thus convergent. But this is not clear for $d>1$ (even for $d=2$)! Any comments or references will be very much appreciated!

PS: This problem does not seem deep, but I still have not found a complete answer after discussing with people.

• A convex function need not be differentiable everywhere. If $x_n$ is a point where $F$ is not differentiable, then $x_{n+1}$ is not even defined. Do you assume that $F\in C^1$? – Piotr Hajlasz Jul 5 '18 at 17:17
• @PiotrHajlasz Yes. Actually the statement on $\nabla F$ implies implicitly that $F$ is differentiable. – MB2009 Jul 5 '18 at 17:24
• @MB2009: But this does not imply continuity of $\nabla F$. Anyway, apparently a smooth counterexample exists, as I attempt to explain in my answer. (The example discussed there is only $C^{1,1-\epsilon}$ for any $\epsilon > 0$, but you can modify it slightly to get $C^\infty$, if you like). – Mateusz Kwaśnicki Jul 5 '18 at 19:27

(Skip the initial two – or even three – paragraphs for the actual solution).

The equation $$x_{n+1} - x_n = \nabla F(x_n) - x_n$$ seems to be a discretised version of $$x'(t) = \nabla F(x(t)) - x(t).$$ The vector field $\nabla F(x) - x$ is conservative, with scalar potential $|x|^2/2 - F(x)$ which is confining (that is, it goes to $\infty$ at infinity). Thus, the gradient flow will converge to the set of critical points of the potential. In a typical situation, this set is discrete, in which case the answer for the continuous problem is affirmative (although the limit need not be unique: it may depend on the initial value). If, however, you choose a sufficiently nasty potential, the gradient flow may fail to converge.

Now let us try a similar approach for the discrete equation: write $G(x) = |x|^2/2 - \nabla F(x)$, so that $x_{n+1} - x_n = -\nabla G(x_n)$. This is the gradient descent sequence for the function $G$, with a constant parameter. It is well-known that gradient decent may fail to converge if the parameter is too large, compared to the second derivatives of $G$. However, in our case the second derivative of $G$ in any direction is bounded by $1$, which is precisely what we need.

Here the actual solution begins: Write $G(x) = |x|^2/2 - F(x)$, so that $x_{n+1} = x_n - \nabla G(x_n)$. By convexity of $F$, $$G(x) \le G(x_n) + \nabla G(x_n) \cdot (x - x_n) + |x - x_n|^2/2 .$$ Setting $x = x_{n+1}$ leads to \begin{aligned} G(x_{n+1}) & \le G(x_n) + \nabla G(x_n) \cdot (-\nabla G(x_n)) + |\nabla G(x_n)|^2/2 \\ & = G(x_n) - |\nabla G(x_n)|^2/2 . \end{aligned} It follows that $(G(x_n))$ is a (stricly) decreasing sequence, and therefore it converges to a certain limit. In other words, $\sum_n |\nabla G(x_n)|^2 < \infty$, that is, $\sum_{n = 1}^\infty |x_{n+1} - x_n|^2 < \infty$. In particular, $$\lim_{n \to \infty} |\nabla G(x_n)| = \lim_{n \to \infty} |x_{n+1} - x_n| = 0.$$ This implies that the set of accumulation points of $(x_n)$ is connected (see below). Additionally, assuming continuity of $\nabla F$, for every accumulation point $x^* = \lim_{n \to \infty} x_{k_n}$ we have $\nabla G(x^*) = \lim_{n \to \infty} \nabla G(x_{k_n}) = 0$. To summarise:

If $\nabla F$ is continuous and the set of critical points of $|x|^2/2 - F(x)$ is discrete, then the answer is affirmative: $(x_n)$ converges to a critical point of $F$.

Let me remark why the set of accumulation points of a bounded sequence $(x_n)$, satisfying the condition $\lim_{n \to \infty} |x_{n+1} - x_n| = 0$, is connected. Suppose that it is not, that is, it can be divided into two closed parts $F_1$ and $F_2$, whose distance is positive. Let $3 \delta$ denote the distance between $F_1$ and $F_2$. Choose and arbitrary $N > 0$ large enough, so that $|x_{n + 1} - x_n| < \delta$ when $n > N$. There exist elements $x_i, x_k$ such that $N < i < k$, $\operatorname{dist}(x_i, F_1) < \delta$ and $\operatorname{dist}(x_k, F_2) < \delta$. For $j = i, i+1, \ldots, k$ we have $\operatorname{dist}(x_j, F_1) + \operatorname{dist}(x_j, F_2) \ge 3 \delta$, each summand changes by at most $\delta$ when $k$ is replaced by $k + 1$. It is therefore easy to see that for some $k \in \{i + 1, i + 2, \ldots, k - 1\}$ we must have $\operatorname{dist}(x_k, F_1) \ge \delta$ and $\operatorname{dist}(x_k, F_2) \ge \delta$. In other words, for any $N$ there is $k > N$ such that $\operatorname{dist}(x_k, F_1) \ge \delta$ and $\operatorname{dist}(x_k, F_2) \ge \delta$. By choosing a convergent subsequence of these elements $x_k$, we find an accumulation point of $(x_n)$ away from $F_1 \cup F_2$, a contradiction.

OK, I cheated: the actual solution starts here. What happens if the set of critical points of $G(x) = |x|^2/2 - F(x)$ is not discrete? It turns out that $(x_n)$ may fail to converge! It is difficult to describe a counterexample, and I did not check every detail; roughly speaking, the graph of the function $G(x)$ described below is an infinite spiral ramp around the unit disk.

[Edit: I re-wrote the following construction.] We suppose that $d = 2$. We use polar coordinates $(r, t)$ rather than Cartesian ones $(x, y)$. We also write $P_n$ (rather than $x_n$) for the sequence of points defined in the question: $P_{n+1} = P_n - \nabla G(P_n)$.

Step 1. We divide $\mathbb{R}^2$ into five regions:

• 'interior': the unit disk, $D_0 = \{r \le 1\}$;

• 'ramp': the area between two spirals, $D_1 = \{1 + e^{-t} \le r \le 1 + 2 e^{-t} , \, t \ge 0\}$;

• 'walls': everything between the consecutive turns of the ramp, $D_2 = \{1 + 2 e^{-t} < r < 1 + e^{-t + 2 \pi} , \, t \ge 2 \pi\}$;

• 'circus': $D_3 = \{r < 10\} \setminus (D_0 \cup D_1 \cup D_2 \cup D_3) = \{1 + 2 e^{-t} < r < 10 , \, 0 \le t < 2 \pi\}$;

• 'exterior': $D_4 = \{r \ge 10\}$.

Our goal is to define $G$ in such a way that: (A) the second order derivatives of $G$ are small; (B) a particle placed on the ramp and following the recurrence equation $P_{n+1} = P_n - \nabla G(P_n)$ stays on the ramp forever.

Step 2. First of all, we set $G = 0$ in the interior $D_0$ and the exterior $D_4$.

Step 3. We now define $G$ on the ramp $D_1$ in such a way that condition (B) is satisfied: for a fixed $t \ge 0$, if $1 + e^{-t} \le r \le 1 + 2 e^{-t}$, we let $G$ to be a linear function of $r$: $$G = c (e^{-2 t} + a(t) (r - 1 - e^{-t})) ,$$ where $a(t) > 0$ is extremely small. More precisely, we require that if the point $P$ lies on the inner edge of the ramp: $r = 1 + e^{-t}$, then the point $$P' = P - \nabla G(P)$$ also lies on the same curve, a little bit down the ramp. Denote the polar coordinates of $P$ by $t$ and $r = 1 + e^{-t}$, and the polar coordinates of $P'$ by $t'$ and $r' = 1 + e^{-t'}$. At $r = 1 + e^{-t}$ we have $\partial_r G = c a(t)$ and $\partial_t G = -2 c e^{-2 t} + c a(t) e^{-t}$. Our condition reads $$r' \cos(t' - t) = r - \partial_r G(P) , \quad r' \sin(t' - t) = -r \partial_t G(P) ,$$ that is, $$(1 + e^{-t'}) \cos(t' - t) = (1 + e^{-t}) - c a(t) , \quad (1 + e^{-t'}) \sin(t' - t) = c (1 + e^{-t}) (2 e^{-2 t} - a(t) e^{-t}) .$$ Given a small $c > 0$, by the inverse mapping theorem, it looks like we can choose $t'$ and $a(t)$ in such a way that the above condition holds, and $$\begin{gathered} t' - t \sim 2 c e^{-2 t} , \\ a(t) \sim 2 e^{-3t} , \\ a'(t) \sim -6 e^{-3 t} , \\ a''(t) \sim 18 e^{-3 t} . \end{gathered}$$ (I did not work out the details here). The above properties of $a(t)$ imply that the second order derivatives of $G$ are bounded by a constant times $c$ on $D_1$.

Step 4. We now build the walls for our ramp: we define $G$ in $D_2$. For $t \ge 2 \pi$ and $1 + 2 e^{-t} < r < 1 + e^{-t + 2 \pi}$ we let $G$ to be the cubic polynomial in $r$ which matches the values and the derivatives of $G$ with respect to $r$ at the boundary values $r_0 = 1 + 2 e^{-t}$ and $r_1 = 1 + e^{-t + 2 \pi}$, defined already in Step 3. The formula for $G$ can be given explicitly in terms of $t$, $a(t)$ and $a(t - 2 \pi)$. The important thing is that the second derivative of $G$ with respect to $r$ is bounded by the ratio of the 'height of the wall' (which is at most $c e^{-2 t} (e^{2 \pi} - 1)$) to the square of the 'width of the wall' (which is $e^{-t} (e^{2 \pi} - 2)$) plus the ratio of $a(t)$ to the 'width of the wall'. Thus, it is bounded by a constant times $c$. Similarly, one can bound second order derivatives of $G$ in any direction at all points of $D_2$ (and again I did not work out the details).

Step 5. We need to extend $G$ to the circus $D_3$. Since this is a nice domain, and we have already defined $G$ elsewhere so that it has second order derivtives bounded by a constant times $c$, we can define $G$ in $D_3$ in such a way that the bound on the second order derivatives remains the same (possibly with a larger constant).

Step 6. Now we are ready to eventually choose $c$: we make it small enough, so that the second derivatives of $G$ are in fact bounded by $1$. And we eventually define $F = r^2/2 - G$.

Now $F$ is convex (because the second derivatives of $F$ in any direction belong to the interval $(0, 2)$) and $F(r e^{i t}) = r^2 / 2$ for $r \ge 10$. There is one more step needed to assert that $\nabla F$ is bounded: we modify $F(r e^{i t})$ for $r \ge 10$ and we set $F(r e^{i t}) = 10 (r - 10)$ for $r \ge 10$. This of course does not affect convexity of $F$.

End of the construction. By property $(B)$, if $P_0$ corresponds to $t = 0$ and $r = 1 + e$ (which lies on the inner edge of the ramp $r = 1 + e^{-t}$), then $P_n$ corresponds to $t_n$ and $r_n = 1 + e^{-t_n}$ for some $t_n > 0$. Additionally, $t_{n+1} - t_n = t_n' - t_n \sim 2 c e^{-2 t_n}$, and hence $t_{n+1} - t_n \to 0$ and $t_n \to \infty$. Therefore, $(P_n)$ is not convergent.

I am still not satisfied with the above description (and the quality of the image). If you are able to simplify it, feel free to edit this answer.

• Thank you very kindly for the reply, and I find it a very elegant answer. Could you please explain a bit more where the set of accumulation points of $(x_n)$ is connected? Also, I'd like to confirm in your claim that, the set of critical points is discrete (NOT FINITE). Thanks again! – MB2009 Jul 6 '18 at 8:42
• @MB2009: I meant discrete (that is, with no accumulation points). However, since we know in advance that $\nabla F$ is bounded, this does not really make any difference: all critical points of $\nabla G$ are contained in a bounded set, and therefore "discrete" is equivalent to "finite". I added some explanation regarding connectedness of the set of accumulation points. – Mateusz Kwaśnicki Jul 6 '18 at 9:30
• Thanks a lot for the prompt reply. I'm reading your constructed example, and have some questions: 1) What does "the point $G((1+e^{-t})e^{it})-\nabla G((1+e^{-t})e^{it})$ also lies on the same spiral $(1+e^{-s})e^{is}$" mean? – MB2009 Jul 6 '18 at 13:53
• 2) Here the polar coordinate is applied, is the gradient $\nabla G$ still corresponding to $(x,y)$ instead of $(r,t)$? – MB2009 Jul 6 '18 at 13:57
• 3) The function $G$ is constructed by distinguishing $r\le 1$, $1+e^{-t}\le r< 1+2e^{-t}$, $1+2e^{-t}\le r< 1+e^{-t+2\pi}$ and $r\ge 10$. Is it correct? – MB2009 Jul 6 '18 at 14:02