Is the maximum function Lipschitz continuous?

Question

Suppose $f(x)=\max_{1\le i\le N}\{x_i\}$, where $x$ is an $N$-dimensional vector. Is the function $f$ Lipschitz continuous?

Answer 1

You have $$|f(x)-f(y)| = |\max_{1\le i \le N} x_i - \max_{1\le i \le N} y_i| \overset{(*)}\le \max_{1\le i \le N} |x_i-y_i| = \|x-y\|_\infty.$$ So if you are using the metric $$d_\infty(x,y) = \|x-y\|_\infty = \max_{1\le i \le N} |x_i-y_i|$$ (sometimes also called Chebyshev distance), then you are done.

If you are using some other metric $d(x,y)$ it only remains to show that $d_\infty(x,y) \le C d(x,y)$ for some constant $C$. (Which is true for the commonly used metrics on $\mathbb R^N$.)

---

To see that the inequality marked $(*)$ holds you can argue as follows.

Let us assume that $\max x_i \ge \max y_i$. In this case we have $|\max x_i-\max y_i|=\max x_i-\max y_i$.

Let us denote by $i_0$ the index $i_0\in\{1,2,\dots,N\}$ such that $x_{i_0}=\max x_i$. Then we have $$\max x_i-\max y_i = x_{i_0} - \max y_i \overset{(1)}\le x_{i_0} - y_{i_0} \le \max (x_i-y_i) \le \max |x_i-y_i|.$$ (The inequality $(1)$ holds since $y_{i_0} \le \max y_i$ and, therefore, $-\max y_i \le -y_{i_0}$.)

The case $\max y_i \ge \max x_i$ is symmetric.