# Max operator over a lipschitz function is still lipschitz?

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

• In the first passage a couple of "$\max$" are missing. – user228113 Nov 22 '17 at 9:12
• is that correct now? – Sam Nov 22 '17 at 9:21
• 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. – 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|$$
• 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. – Sam Nov 22 '17 at 10:04