3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – ProAmateur
    Commented Jan 10, 2023 at 23:29
  • $\begingroup$ Thanks for responding. No, I really meant the $\arg \max$ (and not the $\max$). $\endgroup$
    – MMM
    Commented Jan 10, 2023 at 23:57
  • 3
    $\begingroup$ 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 $\endgroup$
    – ProAmateur
    Commented Jan 11, 2023 at 16:59
  • $\begingroup$ 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)|$. $\endgroup$
    – MMM
    Commented Jan 11, 2023 at 22:01
  • $\begingroup$ I think my counterexample satisfies your monotonicity property... $\endgroup$
    – ProAmateur
    Commented Jan 11, 2023 at 23:32

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .