Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
show 4 more comments

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}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.