# Properties of the maximum of a multivariate Lipschitz function

Let $$g:[0,1] \times [0,1 ] \to \mathbb{R}$$ be a $$K$$-Lipschitz function (w.r.t. the $$\ell_1$$-norm). Consider the maximal function $$f(x) = \arg \max_{y\in [0,1]} g(x, y).$$

I'm interested in what can be inferred about the function $$f$$. In particular, is the function $$f$$ itself $$K$$-Lipschitz? If not, is there a way to bound the difference $$|f(x_1) - f(x_2)|$$? (Does $$f$$ have any other interesting properties?)

Edit: As @madnessweassley pointed out, in general $$f$$ is not Lipschitz. As a result, I'm wondering whether assumptions such as monotonicity of the max help: Assume $$g$$ satisfies that if $$x \geq x'$$, then $$\max_{y\in [0,1]} g(x, y) \geq \max_{y\in [0,1]} g(x', y).$$

Edit 2: After some thought, the question now is more generally: What conditions must we impose on $$g$$ so that $$f$$ is also $$K$$-Lipschitz (or Lipschitz w.r.t. a slightly different constant)?

• Did you mean to define $f(x) = \max_{y \in [0,1]} g(x,y)$? If yes, we can write $\lvert f(x_1) - f(x_2) \rvert = \lvert \max_{y \in [0,1]} g(x_1,y) - \max_{y \in [0,1]} g(x_2,y) \rvert \leq \max_{y \in [0,1]} \lvert g(x_1,y) - g(x_2,y) \rvert \leq \max_{y \in [0,1]} K \lVert x_1 - x_2 \rVert_1 = K \lVert x_1 - x_2 \rVert_1$. Commented Jan 10, 2023 at 23:29
• Thanks for responding. No, I really meant the $\arg \max$ (and not the $\max$).
– MMM
Commented Jan 10, 2023 at 23:57
• I don't think you can expect $f$ to be Lipschitz in that case. A simple counterexample: $g(x,y) = (x-0.5)y$. Then we have $f(x) = \begin{cases} 0, & \text{if } 0 \leq x < 0.5 \\ [0,1], & \text{if } x = 0.5 \\ 1, & \text{if } 0.5 < x \leq 1 \end{cases}$. Note that in general, $f$ is a set-valued mapping. You could expect $f$ to be locally Lipschitz under some rather strict conditions, e.g., see Chapter 6.3 of this book Commented Jan 11, 2023 at 16:59
• Thanks for the interesting counterexample. Please also see my edit, if you have a guess whether such monotonicity assumption is enough for Lipschitzness or other ways to bound $|f(x_1) - f(x_2)|$.
– MMM
Commented Jan 11, 2023 at 22:01
• I think my counterexample satisfies your monotonicity property... Commented Jan 11, 2023 at 23:32

As I noted in the comment, Theorem 6.2 of these notes state sufficient conditions under which $$f$$ is locally Lipschitz at $$\bar{x} \in (0,1)$$ in a suitable sense. I'm reproducing the result below.
Theorem 6.2 of Still: Suppose $$g$$ is twice continuously differentiable and $$\bar{y}$$ is a strict local maximizer of $$\max_{y \in [0,1]} g(\bar{x},y)$$ of order two. Then, there are constants $$\varepsilon, \delta, L > 0$$ such that for all $$x \in B_{\varepsilon}(\bar{x})$$, there exists a local maximizer $$y(x)$$ of $$\max_{y \in [0,1]} g(x,y)$$ satisfying $$\lVert y(x) - \bar{y} \rVert \leq L \lVert x - \bar{x} \rVert$$ (i.e., $$f$$ is locally Lipschitz at $$\bar{x}$$ with local Lipschitz constant $$L$$ in an appropriate sense).