2
$\begingroup$

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

  • 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$.2011-05-03

1 Answers 1

4

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.

  • 0
    Thank you, now I fully understood it.2011-05-03