# Simple proof? If $x$ lies outside a compact convex set, there exists a $y$ closer to every point in the set than $x$.

This seems rather obvious intuitively, but I can't find a simple proof.

If $C$ is a compact, convex subset of $\mathbb{R}^n$ and $x \not \in C$, then there exists a point $y$ such that, for every $c$ in $C$, $\|c-y\| < \|c-x\|$.

(Related question asks to show that for every $x,c$ there exists such a $y$; this asks for a single $y$ that works for all $c$.)

If it simplifies the proof, it's also interesting to prove the following instead:

If $C$ is a finite subset of $\mathbb{R}^n$ and $x$ is not in the convex hull of $C$, then there exists a $y$ such that, for every $c \in C$, $\|c-y\| < \|c-x\|$.

Here's an argument that I think works for the second one, but might be a pain to formalize: Let $S$ be a separating hyperplane between $x$ and $C$. Take the intersection of $S$ with the ball centered at a point $c \in C$ with radius $\|x-c\|$. This is nonempty: Otherwise, $c$ must lie on the "other side" of $S$, a contradiction. Do this for every $c \in C$ iteratively; at each step, the argument holds, so we are left with a nonempty set of points $y$ that satisfy the criteria.

The problem with the proof is formalizing this notion that $c$ must lie on the other side of $S$. Can anyone help me fix/finish the proof, or suggest a better one? Also, I don't think this proof will extend easily to the first case, so that would be interesting to consider as well.

-
You can probably prove that any point on the segment joining $x$ to its projection $p_C(x)$ on $C$ works. – Olivier Bégassat Feb 3 '13 at 22:39
This actually holds for every Hilbert space. – Euler....IS_ALIVE Feb 3 '13 at 23:26

Let $p=p_C(x)$ be the projection of $x$ on $C$. It is the unique point $c\in C$ such that $\vert x-c\vert=d(x,C)$; also, for any $c\in C$ one has $\langle c-p\mid x-p\rangle\leq 0$, and this alone already caracterises $p\in C$. From this caracterisation, it follows that $p$ is the projection on $C$ of any point $y\in [p,x]$ (since $y-p$ is proportioanl to $x-p$ by a nonnegative factor, so the scalar products remain nonpositive.)

Now let us define $y$ as the midpoint of the segment $[p,x]$. Let $c\in C$. Developping the square distance from $x$ to $c$ gives $$\vert x-c\vert^2=\vert x-y\vert^2+\vert y-c\vert^2+2\langle x-y\mid y-c\rangle$$ The scalar product is positive, indeed $$\begin{array}{ccl}\langle x-y\mid y-c\rangle &=&\langle y-p\mid y-c\rangle\\ &=&\langle y-p\mid y-p\rangle+\langle y-p\mid p-c\rangle\\ &=&\vert y-p\vert^2-\langle y-p\mid c-p\rangle\\ &\geq&\vert y-p\vert^2\\ &>&0 \end{array}$$ We are now done in showing that $y$ lies closer to any given point in $C$ than $x$ does, for $$\vert x-c\vert^2=\underbrace{\vert x-y\vert^2+2\langle x-y\mid y-c\rangle}_{>0}+\vert y-c\vert^2>\vert y-c\vert^2$$ Thus, the midpoint $y$ of $[x,p]$ works.

-
Should the first line be "minus" $2\langle x-y \mid y-c \rangle$? – usul Feb 3 '13 at 23:52
@usul no, it's a plus! – Olivier Bégassat Feb 4 '13 at 0:26
Oh, ok, I drew out the vectors and I think I see! Great, thanks! – usul Feb 4 '13 at 0:31
@usul Happy to have been of assistance :) – Olivier Bégassat Feb 4 '13 at 0:33

I dont know if this is a easy way, but you can do like this. Because your set $C$ is closed and convex, you can find $c\in C$ such that $d(x,C)=d(x,c)$ where $d$ denotes distance. Now you can take the segment $[x,c]$. It is easy to see that any point in this segment, excpet $c$ and $x$ will do the job.

-
What does $d(y,C)$ mean? – usul Feb 3 '13 at 22:44
Has $y$ been given yet, then? I was thinking along the same lines of @Olivier. Will post soon. – HSN Feb 3 '13 at 22:45
Sorry it is not $y$, it is $x$. – Tomás Feb 3 '13 at 22:46
$d(y,C)=\displaystyle\inf_{c\in C}d(y,c)$ – Tomás Feb 3 '13 at 22:48
Oh I see, thanks. – usul Feb 3 '13 at 22:48

I accepted Olivier's answer, but I think I can also jump off of it to show concisely that the projection of $x$ onto $C$ works.

Let $p$ be the projection of $x$ onto $C$; we have that, for all $c \in C$, $\langle c - p \mid x - p \rangle \leq 0$.

Then for any $c \in C$, \begin{array}{cl} |x-c|^2 &= |c-p|^2 + |x-p|^2 - 2 \langle c-p \mid x-p \rangle \\ &\geq |c-p|^2 + |x-p|^2 \\ &> |c-p|^2 . \end{array}

-