# Characterization of Lipschitz derivative

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.

• 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. Aug 18, 2021 at 7:07
• 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. Aug 18, 2021 at 7:58
• @Jose27: I see your first point. In my mind, $O$ was convex, I have added this to the question.
– gerw
Aug 18, 2021 at 8:25

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.