Properties of the maximum of a multivariate Lipschitz function

172 Views Asked by At

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)?

1

There are 1 best solutions below

0
On BEST ANSWER

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

Definition 2.1 of Still defines what is a strict local maximizer of order two, and Theorem 2.4 therein identifies sufficient conditions for a local maximizer to be a strict local maximizer of order two.