5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Piotr Hajlasz Jul 5 '18 at 17:17
  • $\begingroup$ @PiotrHajlasz Yes. Actually the statement on $\nabla F$ implies implicitly that $F$ is differentiable. $\endgroup$ – MB2009 Jul 5 '18 at 17:24
  • $\begingroup$ @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). $\endgroup$ – Mateusz Kwaśnicki Jul 5 '18 at 19:27
4
$\begingroup$

(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\}$.

sketch

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – MB2009 Jul 6 '18 at 8:42
  • $\begingroup$ @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. $\endgroup$ – Mateusz Kwaśnicki Jul 6 '18 at 9:30
  • $\begingroup$ 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? $\endgroup$ – MB2009 Jul 6 '18 at 13:53
  • $\begingroup$ 2) Here the polar coordinate is applied, is the gradient $\nabla G$ still corresponding to $(x,y)$ instead of $(r,t)$? $\endgroup$ – MB2009 Jul 6 '18 at 13:57
  • $\begingroup$ 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? $\endgroup$ – MB2009 Jul 6 '18 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.