# Properties of a convex set

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.)

-
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
@abel: no that's what user3123 is looking for. – t.b. May 3 '11 at 18:32
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
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
show 3 more comments

## 1 Answer

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.

-
 Thank you, now I fully understood it. – Listing May 3 '11 at 19:16