In $\mathbb{R}^\mathbb{N}$: Simultaneous distance reduction to points in $A$ possible iff outside closed convex hull spanned by $A$

70 Views Asked by At

I'm working on a problem, and have managed to reduce it to this proposition:

Consider $\mathbb{R}^\mathbb{N}$ with the following distance function that has $\infty$ as a possible value: $d(x,y)=\sum_{i=1}^\infty (x_i-y_i)^2$. Given a set of points $A$ all of which are within finite distance of each other, say that a point $y$ dominates $x$ if for all points $a\in A$, the distance between $a$ and $y$ is smaller than that between $a$ and $x$. Also, say that a point is dominated if there is a point that dominates it. A point is dominated iff it does not belong to the closure of the convex hull spanned by $A$.

I think this is true and I also suppose that it exists as a theorem in the literature to which I can refer; or, failing that, that is a fairly simple corollary of such a theorem. However, I have not been able to find it - perhaps because I don't know the right search terms. Can anyone please help?

1

There are 1 best solutions below

0
On BEST ANSWER

First note that the statement is true when $A=\emptyset$, but also we find weird statements like "$x$ dominates $x$", which I'd like to avoid, are actually true in this case, so assume $A \neq \emptyset$.

By replacing $A$ with $A-a$ for some $a \in A$, we may assume $A \subseteq \ell^2(\mathbb{R})$. Then the closed convex hull $\overline{\mathrm{co}}(A)$ is also a subset of $\ell^2(\mathbb{R})$ and every point of $\mathbb{R}^\mathbb{N}\setminus \ell^2(\mathbb{R})$ is dominated by any point of $\ell^2(\mathbb{R})$. This allows us to replace $\mathbb{R}^\mathbb{N}$ with the much better behaved $\ell^2(\mathbb{R})$ (for which I'll just write $\ell^2$ from now on)

Additionally, as a corollary of the Hahn-Banach separation theorem and the fact $\ell^2$ is a Hilbert space, we have the following characterization of the closed convex hull: $$x \in \overline{\operatorname{co}}(A) \iff \forall y \in \ell^2, \forall C \in \mathbb{R}, \Big(\big(\forall a \in A, \langle y, a\rangle \leq C\big) \implies \langle y, x\rangle \leq C\Big)$$


$(\Rightarrow)$: Suppose $x \in \ell^2$ is dominated. Then we may choose $y \in \ell^2$ such that $\|y-a\|^2 < \|x-a\|^2$ for every $a \in A$. Equivalently, $$\forall a \in A, \quad \langle x-y, a\rangle < \frac{\|x\|^2-\|y\|^2}2$$ If $x \in \overline{\mathrm{co}}(A)$, then by the above characterization, we'd have $$\langle x-y, x\rangle \leq \frac{\|x\|^2 - \|y\|^2}2$$ or equivalently $\|x-y\|^2 \leq 0$. Then $y=x$, but this implies $x$ dominates $x$, which is a contradiction since $A\neq \emptyset$. We conclude $x \not\in \overline{\mathrm{co}}(A)$.


$(\Leftarrow)$: Suppose $x \not\in \overline{\mathrm{co}}(A)$. Then by the above characterization, there is some $y \in \ell^2$ and $C \in \mathbb{R}$ such that $\langle y, a\rangle \leq C$ for every $a \in A$ and $\langle y, x\rangle > C$. Note $y\neq 0$ and define $$z = x-\left(\frac{\langle y,x \rangle-C}{\|y\|^2}\right)y.$$ Then for any $a \in A$, $$\begin{align*}\|z-a\|^2-\|x-a\|^2 &= \left\|x-\left(\frac{\langle y,x \rangle-C}{\|y\|^2}\right)y-a\right\|^2 -\|x-a\|^2\ \\ &= \frac{\langle y,x\rangle - C}{\|y\|^2}\Big(2(\langle y,a \rangle-C)+(C-\langle y, x\rangle)\Big) \\ &< 0\end{align*}$$ so that $z$ dominates $x$.