0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Yes, but also check the case in which one point is in each piece. $\endgroup$ May 20, 2020 at 22:29
  • $\begingroup$ @Ramita I don't know how to prove it. I'm looking for a textbook on this issue. $\endgroup$ May 20, 2020 at 22:33
  • $\begingroup$ There is no well known theorem but it is not difficult to prove either. For the above it is $\sqrt{5}$ with the Euclidean norm. $\endgroup$
    – copper.hat
    May 20, 2020 at 22:36
  • $\begingroup$ @copper.hat I find a theorem of the vector-valued form for this issue, threesquirrelsdotblog.com/2018/03/16/…, and I feel the proof not easy. I want to cite such results, but I can not find any textbook that contain this issue. And it is not proper for me to cite a website. $\endgroup$ May 21, 2020 at 10:37

1 Answer 1

0
$\begingroup$

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})$.

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