Lipschitz constant of continuous and piecewise linear functions

Question

I want to calculate the Lipschitz constant of a continuous and piecewise linear function $f:[0,1]^2\rightarrow R$, like this \begin{equation*} f(x_1,x_2)=\left\{ \begin{aligned} 2x_1+x_2, &\quad\text{if} \quad x_1+x_2\leq 1\\ x_1+1, &\quad\text{if} \quad x_1+x_2>1 \end{aligned} \right. \end{equation*} I guess it is equal to the greatest Lipschitz constant among all pieces. Is there any textbook that contain related theorem?

Answer 1

The problem has lots of structure, so there are many ways of approaching it. Here is one way:

Note that $f(x_1,x_2) = \min (2 x_1+x_2,x_1+1)$.

To see that the $\min$ of Lipschitz functions is Lipschitz:

Suppose $f_1,...,f_m$ are Lipschitz with rank $L$, then $f_k(x)-f_k(y) \le L \|x-y\|$ for all $k,x,y$. Then $\min_i f_i(x)-f_k(y) \le L \|x-y\|$ and choosing $k$ such that $\min_j f_j(y) = f_k(y)$ we see that $\min_i f_i(x)-\min_j f_j(y) \le L \|x-y\|$. Swapping $x,y$ shows that $\min_k f_k$ is Lipschitz with rank $L$. (This result is true more generally, but the finite case contains the basic idea.)

Note that $x \mapsto 2x_1+x_2$ has Lipschitz rank $\sqrt{5}$ and $x \mapsto x_1+1$ has Lipschitz rank $1$, so the smallest $L$ that will work is $L= \max(1,\sqrt{5})$.