The Lipschitz constant of the combination of distance functions used to separate two sets

372 Views Asked by At

Given closed, disjoint sets $C, D$ in a metric space $(X, d)$, we define $f: X \to \mathbb{R} $ by $$x \mapsto \dfrac{d(x, D)}{d(x, D) + d(x, C)}$$

I know that $d(x, C)$ and $d(x, D)$ are $1$-Lipschitz and that $f$ is continuous. I am having trouble showing that $f$ is $1$-Lipschitz (I suspect it is but not sure).

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming that the distance between two sets, $\rho:=d(C, D)$, is positive, the function $f$ is Lipschitz with the constant $1/\rho$. This constant cannot be improved, since $f=0$ on $D$ and $f=1$ on $C$. (For the same reason, $f$ is not Lipschitz when $\rho=0$.)

Proof. Let $Z$ be the plane $\mathbb{R}^2$ with the maximum norm, $\|(u, v)\|_\infty = \max(|u|, |v|)$. The function $f$ is the composition of two maps, $$ g:X\to Z, \qquad g(x)= (d(x, C), d(x, D)) $$ and $$ h:Z\to \mathbb{R}, \qquad h(u, v) = \frac{v}{u+v} $$ Thus, the Lipschitz constant of $f$ is at most the Lipschitz constant of $g$ times the Lipschitz constant of $h$.

The triangle inequality implies that $g$ is $1$-Lipschitz (this is why the maximum norm is used there; Euclidean would be a little wasteful). So it remains to estimate the Lipschitz constant of $h$ on the range of $g$. The range of $g$ is contained in the set $$ P = \{(u, v) : u\ge 0, \ v\ge 0, \ u+v\ge \rho\} $$

Lemma: the Lipschitz constant of a differentiable function on a convex subset of a normed linear space $Z$ is the supremum of the $Z^*$-norm of its gradient. (Note: the gradient of a function on $Z$ takes values in the dual space $Z^*$.)

Proof of the lemma: the mean value theorem says $f(p)-f(q) = \langle \nabla f(\xi), p-q\rangle$ for some $\xi$ between $p$ and $q$. Here the angle brackets denote dual pairing, and $|\langle \nabla f(\xi), p-q\rangle|\le \|\nabla f(\xi)\|_{Z^*}\|p-q\|_Z$ by the definition of dual norm. $\quad\Box$

Going back to our $h$, compute $$ \nabla h(u, v) = \left( \frac{-v}{(u+v)^2}, \frac{u}{(u+v)^2} \right) $$ The dual to the maximum norm is the $1$-norm $\|(\alpha, \beta)\|_1 = |\alpha|+|\beta|$. Since $$ \|\nabla h(u, v)\|_1 = \frac{v}{(u+v)^2} + \frac{u}{(u+v)^2} = \frac{1}{u+v} \le \frac{1}{\rho} $$ for every $(u, v)$ in $P$, the claim is proved.