3
$\begingroup$

Let $f \colon O \to \mathbb R$ be continuously differentiable, where $O \subset \mathbb R^n$ is open and convex. Then, the following two assertions are equivalent:

  1. $\nabla f$ is Lipschitz-continuous with constant $1$, i.e., $$ \| \nabla f(y) - \nabla f(x) \| \le \| y - x \| \qquad \forall x,y \in O.$$
  2. we have $$ \bigl| (\nabla f(y) - \nabla f(x) )^\top (y - x) \bigr| \le \|y - x\|^2 \qquad\forall x,y \in O.$$

I am looking for a concise proof or a reference for this equivalence.

The direction $1 \Rightarrow 2$ is just an application of the Cauchy-Schwarz inequality.

The other direction is slightly harder. Let me outline a proof. If we assume additionally $f \in C^2$, then by using $y = x + t h$, with fixed $h \in \mathbb R^n$ in 2, we obtain $$ |h^\top \nabla^2f(x) h| \le \| h \|^2 \qquad\forall x \in O, h \in \mathbb R^n$$ by passing to the limit $t \to 0$. Since $\nabla^2 f(x)$ is symmetric, this yields $\| \nabla^2 f(x) \| \le 1$ and the Lipschitz continuity of $\nabla f$ follows. In the general case, one can apply this argument to the mollification $f_\epsilon = f \mathbin\star \psi_\epsilon$, where $\psi_\epsilon$ is a standard mollifier.

Is it possible give a direct proof of $2 \Rightarrow 1$ without the 'detour' to $C^2$-functions?

By the way: Although the statements 1 and 2 only depend on $\nabla f$, the equivalence no longer holds if $\nabla f$ is replaced by an arbitrary, continuous function $g \colon O \to \mathbb R^n$: Use, e.g., $g(x) = A x$, where $A \in \mathbb R^{n \times n}$ is skew symmetric.

$\endgroup$
3
  • $\begingroup$ I'm not sure how much you care about this technicality, but for your proof of $2\Rightarrow 1$ we need some regularity of $O$. If $O$ approaches a portion of its boundary from two different sides, then you can't guarantee that bounded derivative implies a Lipschitz condition. $\endgroup$
    – Jose27
    Commented Aug 18, 2021 at 7:07
  • $\begingroup$ It seems to me that your argument is showing that when we replace $\nabla f$ for $g$, then we get $\| D_{\text{symm}}g(z)\| \leq 1$, where $D_{\text{symm}} g$ is the symmetric part of the derivative of $g$. Of course, as in your example, this is not always enough to get something, so the symmetry of $D^2f$ has to come into play somehow; to me this suggests that we're not going to avoid taking that second derivative in some way. $\endgroup$
    – Jose27
    Commented Aug 18, 2021 at 7:58
  • $\begingroup$ @Jose27: I see your first point. In my mind, $O$ was convex, I have added this to the question. $\endgroup$
    – gerw
    Commented Aug 18, 2021 at 8:25

1 Answer 1

5
+200
$\begingroup$

By the fundamental theorem $$ f(y) - f(x) - \nabla f(x)^T(y-x) = \int_0^1 (\nabla f(x+t(y-x))-\nabla f(x))^T(y-x) dt. $$ Let me first prove the claim for $O=\mathbb R^n$. Using (2) this implies $$ |f(y) - f(x) - \nabla f(x)^T(y-x)| \le \frac12 \|y-x\|^2. $$ Now take $d\in \mathbb R^n$. Then the inequality above implies $$ f(y+d) - f(x) - \nabla f(x)^T(y+d-x) \le \frac12 \|y+d-x\|^2\\ f(x-d) - f(y) - \nabla f(y)^T(x-d-y) \le \frac12 \|y+d-x\|^2\\ -(f(y+d) - f(y) - \nabla f(y)^Td) \le \frac 12\|d\|^2\\ -(f(x-d) - f(x) - \nabla f(x)^T(-d)) \le \frac 12\|d\|^2. $$ Addding all these inequalities results in $$ (\nabla f(x) - \nabla f(y))^T(x-y-2d) \le \|y+d-x\|^2 + \|d\|^2. $$ Let me set $g:=\nabla f(x) - \nabla f(y)$ and choose $d$ such that $x-y-2d=g$. Then $d = \frac12(x-y-g)$ and $y+d-x = -\frac12(x-y+g)$. This results in $$ \|g\|^2 \le \frac14\|x-y+g\|^2 + \frac14\| x-y-g\|^2 =\frac12 \|x-y\|^2 + \frac12\|g\|^2, $$ which implies (1).


Let now $x,y\in O\ne \mathbb R^n$. Then $B_\rho(x),B_\rho(y)\subset O$ for some $\rho>0$. In addition, $B_\rho(\lambda x+(1-\lambda y))\subset O$ for all $\lambda \in (0,1)$. Now take $\tilde x,\tilde y$ on the line between $x$ and $y$ such that $\|\tilde x-\tilde y\|<\rho$. Take $d$ such that $\tilde y+d,\tilde x-d\in O$.

As above, we get $$ (\nabla f(\tilde x) - \nabla f(\tilde y))^T(\tilde x-\tilde y-2d) \le \|\tilde y+d-\tilde x\|^2 + \|d\|^2. $$ Denote $\tilde g:=\nabla f(\tilde x) - \nabla f(\tilde y)$. Now I would like to set $d:=\frac12(\tilde x-\tilde y - t\tilde g)$ for some $t>0$ small. Note $$ \tilde y+d = \frac12(\tilde x+\tilde y) -\frac t2 \tilde g,\quad \tilde x-d = \frac12(\tilde x+\tilde y) +\frac t2 \tilde g. $$ Hence it is enough to choose $t := \min(1,\frac\rho{\|\tilde g\|})$. Putting the choice of $d$ in above inequality results in $$ t \|\tilde g\|^2 \le \frac14\|\tilde x-\tilde y+\tilde g\|^2 + \frac14\| \tilde x-\tilde y-\tilde g\|^2 =\frac12 \|\tilde x-\tilde y\|^2 + \frac{t^2}2\|\tilde g\|^2. $$ If $t=\frac\rho{\|\tilde g\|}$ then $$ \rho \|\tilde g\| \le \frac12 \|\tilde x-\tilde y\|^2 + \frac{\rho^2}2 < \rho^2. $$ Then $\|\tilde g\|<\rho$, and $t=1<\frac\rho{\|\tilde g\|}$, a contradiction. Hence $t$ is equal to $1$, and $$ \|\nabla f(\tilde x) - \nabla f(\tilde y)\| \le \|\tilde x-\tilde y\| $$ for all $\tilde x,\tilde y$ on the line between $x$ and $y$ such that $\|\tilde x-\tilde y\|< \rho $.

Now let $n>\frac{1}\rho\|x-y\|$. Divide the line between $x$ and $y$ into $n$ parts of equal length. Set $x_i:=x+\frac in(x-y)$, $i=0\dots n$. Then $\|x_i-x_{i+1}\|<\rho$ and hence $\|\nabla f(x_i) - \nabla f(x_{i+1})\| \le \|x_i-x_{i+1}\|$. Then $$ \|\nabla f(x)-\nabla f(y) \le \sum_{i=0}^{n-1} \|\nabla f(x_i) - \nabla f(x_{i+1})\| \\ \le \sum_{i=0}^{n-1}\|x_i-x_{i+1}\| \\ = \|x-y\|, $$ which finishes the proof.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .