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: (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.
