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

  • 2
    This result is called *supporting hyperplane theorem*. You can find a proof on page 4 of [these slides](https://netfiles.uiuc.edu/angelia/www/L7_separationthms.pdf). 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.2011-05-03
  • 0
    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?2011-05-03
  • 0
    That's the [supporting hyperplane theorem](http://en.wikipedia.org/wiki/Supporting_hyperplane), right?2011-05-03
  • 0
    you are looking for the support plane at the point $y$ for the convex set $c$ and $e$ would be the unit vector orthogonal to that support plane. i am assuming that you know the proof for the existence of a support plane at boundary points of any convex set.2011-05-03
  • 1
    @abel: no that's what user3123 is looking for.2011-05-03
  • 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$.2011-05-03
  • 0
    Thank you for this guide, the two parts I don't know is: a) what is the projection of $x_k$ to $C$? (how it is defined) b) why is $z_k$ in the unit sphere, is it because it is bounded? Also you could write it as a full answer if you want because it will pretty much do the deal for me :-)2011-05-03
  • 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