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.

Let $C \subset \mathbb{R}^n$ be convex and closed, $y \in \partial C$.

Show that there is an affine $f(x)=\langle x-y,e \rangle$ where $|e|=1$, such that $f(y)=0$ and $\forall x \in C: f(x) \leq 0$

Notation: Let me explain my notation, in case there is some confusion: $\langle -,- \rangle$ is the euclidean scalar product and $|\cdotp |$ is the derived norm.

Also I want to add some things I already know that could be interesting here: (1) $\forall v \in \mathbb{R}^n \backslash C: ! \exists c \in C \text{such that} |v-c|=\min_{x \in C}|v-x|$

(2) For $v$ and $c$ like in (1): $\forall x \in C: \langle x-c,\frac{v-c}{|v-c|} \rangle \leq 0$

Geometrically if I am not completely wrong you could imagine $e$ as standing orthogonally on $y$ so the scalar product would be always negative. (Sorry for the awful formatting, I will try to improve my latex-skills! If something is not clear, don't hesitate to ask.)

share|improve this question
2  
This result is called supporting hyperplane theorem. You can find a proof on page 4 of these slides. Note also that your functional $f$ is not linear (since $f(0) = \langle -y, e \rangle \neq 0$ in general) but rather affine. Otherwise, your intuition is quite good, by the way. –  t.b. May 3 '11 at 18:26
    
Thank you for your answer! You are right I corrected it to say affine. But maybe is there a straight forward way to show it from what I already have? –  Listing May 3 '11 at 18:29
1  
@abel: no that's what user3123 is looking for. –  t.b. May 3 '11 at 18:32
1  
To find the vector $e$, you can proceed as follows. Approximate the boundary point $y$ from outside $C$ with a sequence $x_k$ in $C \smallsetminus X$. Let $c_k$ be the projection of $x_k$ to $C$. The sequence $z_k = \frac{x_k - c_k}{\|x_k - c_k\|}$ is a sequence in the compact unit sphere $S^{n-1}$ of $\mathbb{R}^n$. You can therefore extract a convergent subsequence $z_{k_n} \to e \in S^{n-1}$ and you can check that $\langle e,c \rangle \leq \langle e, y \rangle$ for all $c \in C$. –  t.b. May 3 '11 at 18:37
1  
Ok, I'll write it out in a moment. Here's a brief answer first. a) For $v \in \mathbb{R}^n \smallsetminus C$ you have a unique $c \in C$ closest to it by your property (1), write $v_k = x_k$ and $c_k$ is the corresponding point. As for b), just note that $\|z_k\| = 1$. –  t.b. May 3 '11 at 18:51

1 Answer 1

up vote 4 down vote accepted

As I pointed out in the comments, you can find a proof on page 4 in these slides (found by Googling for supporting hyperplane theorem, proof). The slides refer to chapter 2.5 of Boyd and Vanderberghe's book Convex optimization (free download on Boyd's webpage), see pages 46ff of the book.

Using what you know, you can prove it as follows.

  1. Choose a sequence $v_k \in \mathbb{R}^n \smallsetminus C$ such that $v_k \to y$. Such a sequence exists by the property that $y \in \partial C$ and $C$ is a proper closed subset of $\mathbb{R}^n$.

  2. Let $c_k \in C$ be the unique point closest to $v_k$ by (1), so $c_k$ has the property $|v_k - c_k| = \inf_{c \in C} |v_k - c|$.

  3. Moreover, by (2) we know that for all $x \in C$ we have $\displaystyle \left\langle x - c_k, \frac{v_k - c_k}{|v_k - c_k|}\right\rangle \leq 0$ for all $x \in C$.

  4. Put $z_k = \frac{v_k - c_k}{|v_k - c_k|}$. Note that $|z_k| = 1$ so that $z_k \in S^{n-1} = \{y \in \mathbb{R}^{n}\,:\,|y| =1 \}$. The equation in step 3. now reads $\langle x - c_k, z_k \rangle \leq 0$ for all $x \in C$.

  5. Since $S^{n-1}$ is compact, we can extract a convergent subsequence $z_{k_j} \to e \in S^{n-1}$. Note that $|e| = 1$ by definition.

  6. For all $x \in C$ and all $j$ we have $\langle x - c_{k_j}, z_{k_j} \rangle \leq 0$. Now let $j \to \infty$ to obtain $\langle x - y, e \rangle \leq 0$ for all $x \in C$ since $c_{k_j} \to y$ and $z_{k_j} \to e$ and the limit of non-positive numbers is non-positive.

To finish all up, let $f(x) = \langle x - y, e \rangle$ and note that $f$ has all the desired properties, as we established in step 6.

share|improve this answer
    
Thank you, now I fully understood it. –  Listing May 3 '11 at 19:16

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.