I have a function $f:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ which is $L$-Lipschitz (over the Manhattan distance). Is $\max_y f(x,y)$ still Lipschitz? In my opinion, it is true, and I can prove it, but I'm not sure whether the proof is correct or not, because to me seems too easy.

$$ |\max_{y_1} f(x_1,y_1) - \max_{y_2} f(x_2,y_2) | =|\max_{y_1} f(x_1,y_1) - \max_{y_2}\bigl(f(x_1,y_2) - f(x_1,y_2) + f(x_2,y_2)\bigr) | $$

$$ \leq| \max_{y_1} f(x_1,y_1) - \max_{y_2} f(x_1,y_2) + L |x_1 - x_2| | = L|x_1 - x_2|$$

  • $\begingroup$ In the first passage a couple of "$\max$" are missing. $\endgroup$ – user228113 Nov 22 '17 at 9:12
  • $\begingroup$ is that correct now? $\endgroup$ – Sam Nov 22 '17 at 9:21
  • $\begingroup$ Okay, I see the main error. I cannot cancel $\max_{y_1}f(x_1,y_1)$ and $f(x_2,y_2)$ where $y_2 = \mathrm{arg}\max_{y_2}f(x_2,y_2) \neq y_1$. Thus I could say that |\max_{y_1}f(x_1,y_1) - \max_{x_2,y_2}| \leq L(|x_1-x_2| + |y_1 -y_2|) where $y_1$ and $y_2$ are the argmaxs of $f(x_1,y_1)$ and $f(x_2,y_2)$ respectively. Thus I can see that $\max_y f(x,y)$ is not Lipschitz. Thanks to everybody. $\endgroup$ – Sam Nov 22 '17 at 10:01

(1) Define $f_y : \mathbb{R}\rightarrow \mathbb{R}$ by $f_y(x)=f(x,y)$. Hence $$|f_y(x)-f_y(z)|=|f(x,y)-f(z,y)|\leq L |x-z|$$ so that each $f_y$ is $L$-Lipschitz.

(2) Note that $F(x):=\max_y\ f(x,y)$ is a supremum of $f_y$.

(3) Hence if $F(x)>F(z)$, then $$F(x)-F(z)\leq F(x) - f_y(z)$$ where $|F(x)-f_y(x)| <\varepsilon$. That is, $$ F(x)-F(z) \leq \varepsilon + |f_y(x)-f_y(z)| \leq \varepsilon + L|x-z|$$

  • $\begingroup$ with your derivation seems that F(x) is not Lipschitz. Can you please underline what is the mistake I have done in my derivation? otherwise, could be that my derivation has just a tighter bound that your one. $\endgroup$ – Sam Nov 22 '17 at 9:48
  • $\begingroup$ To me, your solution is correct. $\endgroup$ – HK Lee Nov 22 '17 at 9:53
  • $\begingroup$ Sorry HK Lee, but I saw now a mistake on my derivation, and moreover, it seems to me that our derivations are showing exactly opposite results, since in your result $F$ is clearly not Lipschitz. I think your derivation is correct and mine not. $\endgroup$ – Sam Nov 22 '17 at 10:04

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.