3
$\begingroup$

Let $X,Y,Z$ be normed spaces. Let $P\subseteq X$ and $Q\subseteq Y$ be bounded. Endow the product space $X\times Y$ with the $\max$ norm.

Suppose $f:P\times Q\rightarrow Z$ is Lipschitz continuous with Lipschitz modulus $L$.

By way of background, note that by the triangle inequality and $f$'s Lipschitz continuity, for $x_1,x_2\in P,y_1,y_2\in Q$:

$$\begin{align}& \|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\| \\ &\le \min{\{\|f(x_1,y_1)-f(x_1,y_2)\|+\|f(x_2,y_2)-f(x_2,y_1)\|,\\\|f(x_1,y_1)-f(x_2,y_1)\|+\|f(x_2,y_2)-f(x_1,y_2)\|\}} \\ &\le 2L \min{\{\|x_1-x_2\|,\|y_1-y_2\|\}}.\end{align}$$

This bound seems surprisingly weak. For example, if $f$ is actually linear, then the left hand side is always equal to $0$.

Suppose we call $f$ "Doubly Lipschitz" with modulus $K$ if it is Lipschitz and for all $x_1,x_2\in P,y_1,y_2\in Q$:

$$\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\| \le K \|x_1-x_2\|\|y_1-y_2\|.$$

This seems to be a stronger requirement than just Lipschitz continuity, as for $\|x_1-x_2\|\le 1,\|y_1-y_2\|\le 1$, $\|x_1-x_2\|\|y_1-y_2\|\le\min{\{\|x_1-x_2\|,\|y_1-y_2\|\}}$, but the converse does not hold in general.

What else is known about "Doubly Lipschitz" functions? What are they usually called? Do they have a simple characterisation? Does being Doubly Lipschitz relate to membership of a certain Sobolev space?

Answered: Is there a simple example of a function that is Lipschitz but not Doubly Lipschitz?


Addenda 1: "Lipschitz-Quadratic" functions are Doubly Lipschitz.

For $n\in\mathbb{N}$, let $W_n$ be an inner product space, all defined over the same field ($\mathbb{R}$ or $\mathbb{C}$), and suppose $Z$ is this field.

Let $a:X\rightarrow Z$, $b:Y\rightarrow Z$, $C_n:X\rightarrow W_n$ and $D_n:Y\rightarrow W_n$ for $n\in\mathbb{N}$, all be Lipschitz continuous, with $\sum_{n=0}^\infty{\langle C_n(x_0),D_n(y_0)\rangle}<\infty$ for some $x_0\in X$ and $y_0\in Y$. Suppose the Lipschitz moduli of $C_n$ and $D_n$ are $L_{C_n}$ and $L_{D_n}$ respectively, with $\sum_{n=0}^\infty{L_{C_n} L_{D_n}}\le L$ for some $L<\infty$.

Suppose further that:

$$f(x,y)=a(x)+b(y)+\sum_{n=0}^\infty{\langle C_n(x),D_n(y)\rangle}.$$

We call this a "Lipschitz-Quadratic" function.

Then:

$$\begin{align}& \|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\| \\ & \le \sum_{n=0}^\infty{ |\langle C_n(x_1)-C_n(x_2),D_n(y_1)-D_n(y_2)\rangle| } \\ & \le \sum_{n=0}^\infty{ \|C_n(x_1)-C_n(x_2)\|\|D_n(y_1)-D_n(y_2)\| } \\ & \le L \|x_1-x_2\|\|y_1-y_2\|,\end{align}$$

(by the Cauchy Schwarz inequality), as required.

This class encompasses many discontinuous examples, e.g. $f(x,y)=\|x\| \|y\|$.

It also includes smooth examples such as $f(x,y)=\exp{(xy)}$.


Addenda 2: Functions that are uniformly Frechet differentiable in one argument, with the derivative being uniformly Lipschitz continuous in the other are Doubly Lipschitz.

Suppose $f(x,y)$ is Frechet differentiable in $x$ everywhere, uniformly over $y$. I.e. there exists a function $G:P\times Q \rightarrow B(X,Z)$ such that for all $x\in X$:

$$\lim_{x_1\rightarrow x, x_2\rightarrow x}\sup_{y\in Y}{\frac{\| f(x_1,y)-f(x_2,y)-G(x,y)(x_1-x_2)\|}{\|x_1-x_2\|}}=0.$$

Suppose further that $G$ is Lipschitz in $y$, uniformly over $x$. I.e., there exists a constant $K$ such that for all $x\in X$ and $y_1,y_2\in Y$:

$$\|G(x,y_1)-G(x,y_2)\|\le K\|y_1-y_2\|.$$

Given that $\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\|\le 2L \min{\{\|x_1-x_2\|,\|y_1-y_2\|\}}$, it is sufficient to prove that for all $x\in X$ and $y\in Y$:

$$\lim_{x_1\rightarrow x, x_2\rightarrow x,\\y_1\rightarrow y, y_2\rightarrow y}{\frac{\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\|}{\|x_1-x_2\|\|y_1-y_2\|}}<\infty.$$

Now, for $x\in X$ and $y_1,y_2\in Y$:

$$\begin{align}& \lim_{x_1\rightarrow x, x_2\rightarrow x}{\frac{\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\|}{\|x_1-x_2\|}} \\ & = \lim_{x_1\rightarrow x, x_2\rightarrow x}{\left\|\frac{f(x_1,y_1)-f(x_2,y_1)-G(x,y_1)(x_1-x_2)}{\|x_1-x_2\|}\\-\frac{f(x_1,y_2)-f(x_2,y_2)-G(x,y_2)(x_1-x_2)}{\|x_1-x_2\|}\\+\frac{(G(x,y_1)-G(x,y_2))(x_1-x_2)}{\|x_1-x_2\|}\right\|} \\ & \le {\lim_{x_1\rightarrow x, x_2\rightarrow x}{\frac{\|f(x_1,y_1)-f(x_2,y_1)-G(x,y_1)(x_1-x_2)\|}{\|x_1-x_2\|}}\\+\lim_{x_1\rightarrow x, x_2\rightarrow x}{\frac{\|f(x_1,y_2)-f(x_2,y_2)-G(x,y_2)(x_1-x_2)\|}{\|x_1-x_2\|}}\\+\lim_{x_1\rightarrow x, x_2\rightarrow x}{\frac{\|(G(x,y_1)-G(x,y_2))\|\|x_1-x_2\|}{\|x_1-x_2\|}}} \\ & = \|G(x,y_1)-G(x,y_2)\| \end{align}$$

and the convergence here is uniform over $y_1, y_2$, so by the Moore-Osgood theorem:

$$\begin{align}& \lim_{x_1\rightarrow x, x_2\rightarrow x,\\y_1\rightarrow y, y_2\rightarrow y}{\frac{\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\|}{\|x_1-x_2\|\|y_1-y_2\|}} \\ & = \lim_{y_1\rightarrow y, y_2\rightarrow y}\lim_{x_1\rightarrow x, x_2\rightarrow x}{\frac{\|f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\|}{\|x_1-x_2\|\|y_1-y_2\|}} \\ & \le \lim_{y_1\rightarrow y, y_2\rightarrow y}{\frac{\|G(x,y_1)-G(x,y_2)\|}{\|y_1-y_2\|}} \\ & \le K.\end{align}$$

$\endgroup$
6
  • 1
    $\begingroup$ I did not do the calculation, but I would expect that every $C^1$-function with a bounded derivative is “doubly Lipschitz”. Probably even already Gateaux differentiability with a bounded derivative is sufficient. $\endgroup$ Apr 23 '21 at 11:54
  • $\begingroup$ @MartinVäth Yes, this seems plausible. I am more interested in these non-differentiable cases though. The question now contains a second addenda with a function that is non-differentiable but Doubly Lipschitz. Your answer is non-differentiable but not Doubly Lipschitz. Your answer suggests a criteria for dividing between the two cases, it would be great if this was the complete answer. I wonder if being Doubly Lipschitz relates to membership of a Sobolev space. $\endgroup$
    – cfp
    Apr 23 '21 at 12:15
  • 1
    $\begingroup$ The smoothness is certainly only sufficient: As I have written in the answer, my intuition is that for a counterexample the “nondifferentiable peak” must not be parallel along one of the axes. For instance $f(x,y)=g(x)+h(y)$ is “doubly Lipschitz” independent of $g$ and $h$ ($f,g,h$ need not even be Lipschitz!), because the non-smoothness is parallel along the axes, only. $\endgroup$ Apr 23 '21 at 12:34
  • $\begingroup$ @MartinVäth The question now has a broader class of examples. It seems to be as broad as is possible. Can you think of a doubly lipschitz function with scalar Z that is not "Lipschitz-Quadratic"? $\endgroup$
    – cfp
    Apr 27 '21 at 16:47
  • $\begingroup$ @MartinVäth It would be great if you could also take a look at this related (but harder) question: math.stackexchange.com/questions/4118772/… $\endgroup$
    – cfp
    Apr 27 '21 at 18:01
2
$\begingroup$

An example of a Lipschitz function for which the first bound is best possible is in case $X=Y$ the function $f(x,y)=\lVert x-y\rVert$.

Indeed, in case $x_1=y_1=a$, $x_2=y_2=b$, there holds $$\lVert f(x_1,y_1)+f(x_2,y_2)-f(x_1,y_2)-f(x_2,y_1)\rVert=2\lVert a-b\rVert=2\min\{\lVert x_1-x_2\rVert,\lVert y_1-y_2\rVert\}.$$

In particular, this rather non-exotic function already fails to be “doubly Lipschitz”. My intuition is that this is always the case whenever the function has a non-differentiable “peak” along a direction which is not “parallel” to one of the 2 coordinate axes of $X\times Y$.

$\endgroup$

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.