3

Let $\Omega$ be a bounded convex set in $\mathbb{R}^n$, and let $\partial \Omega$ denote its boundary.

Fix a point $p$ in $\Omega$, and let $c$ denote the point on $\partial \Omega$ that is closest to $p$.

Then, intuitively it seems that a hyperplane which goes through $c$ with the noraml vector parallel to the vector from $p$ to $c$ is a supporting hyperplane, but how can one prove or disprove this?

user74261
  • 2,286

2 Answers2

2

I am assuming that $p \neq c$, that is, $p \in \Omega^\circ$, otherwise any vector passes through $c-p$.

The essential idea is that a supporting hyperplace to $\Omega$ at $c$ is also a supporting hyperplane to $B(p,\|c-p\|)$ at $c$, and the direction of this hyperplane is unique.

We use the following technical results:

If $x \in \Omega^\circ$ and $y \in \overline{\Omega}$, then $(1-t)x+ty \in \Omega^\circ$ for all $t \in [0,1)$ (see Theorem 6.1 in Rockafellar's "Convex Analysis", for example).

Note that since $\Omega$ is convex, we have $\partial \Omega = \overline{\Omega} \setminus \Omega^\circ$.

If $y \in \overline{\Omega}^c$ and $y_t = (1-t)p+t y$, then there is some $t^* \in (0,1)$ such that $y_{t^*} \in \partial \Omega$. To see this, let $I = \{ t \in [0,1] | y_t \in \Omega^\circ \}$. Since $\Omega^\circ$ is open and convex, we have $I=[0,t^*)$ for some $t^*$, and we must have $t^* <1$ since $\overline{\Omega}^c$ is open. We see that $y_{t^*} \notin \Omega^\circ$, and $y_{t^*} \in \overline{\Omega}$, hence $y_{t^*} \in \partial \Omega$.

Let $r = \|p-c\|$. By choice of $c$, if $y \in \partial \Omega$, then $\|p-y\| \ge r$. If $y \in \overline{\Omega}^c$, then (from above) $y_{t^*} \in \partial \Omega$, and so $\|p-y_{t^*}\| = t^* \|p-y\| \ge r$, and so $\|p-y\| \ge r$. Since $(\Omega^\circ)^c = \partial \Omega \cup \overline{\Omega}^c$, we see that if $y \in (\Omega^\circ)^c$, then $\|p-y\| \ge r$. Hence we have $B(p,r) \subset \Omega^\circ$.

Now suppose $H = \{x | \langle h, x \rangle = \alpha\}$ is a supporting hyperplane to $\Omega^\circ$ passing through $c$. We may assume $\langle h, p \rangle < \alpha$ and hence $\langle h, x \rangle < \alpha$ for all $x \in \Omega^\circ$. In particular, $\Omega^\circ$ does not intersect $H$, and so $H$ is contained in $(\Omega^\circ)^c$. Hence $\|p-x\| \ge r$ for all $x \in H$. Hence $c$ is the closest point to $p$ in $H$.

That is, $c$ solves $\min \{ {1 \over 2} \|x-p\|^2 | \langle h, x \rangle = \alpha \}$, and Lagrange gives $c-p + \lambda h = 0$, so we see that $c-p$ and $h$ are collinear.

As an aside, this shows that this is the only separating hyperplane that passes through $c$.

copper.hat
  • 172,524
  • The reason that $c$ is the closes point to $H$ in the closure of the ball is because $c$ actually lies on $H$? – user74261 May 18 '15 at 02:40
  • Yes. The hyperplane $H$ passes through $c$, and $c$ also lies in $\overline{B}(p,r)$. Hmm, when I read the answer it is not very clear, let me see if I can improve it a little. – copper.hat May 18 '15 at 04:03
  • I updated the answer and added more detail, hopefully this is better. – copper.hat May 18 '15 at 06:57
  • What do you mean by the set $I = { t \in [0,1] | t^\star \in \Omega^o}$ – user74261 May 18 '15 at 17:51
  • Typo., should be ${t \in [0,1] | y_t \in \Omega^\circ }$. Thanks for catching that. Convex analysis is often intuitively obvious but the analysis detailed. – copper.hat May 18 '15 at 18:00
  • May I also ask you about your claim $I = [0,t^\star)$? My reasoning is that $\Omega^o$ being open gives at least one $t > 0$ in $I$ such that $y_t \in \Omega^o$ and for every such $t$, convexity gives $[0,t] \subset I$. Then, to get $t^\star$, I am guessing that you take the supremum of all such $t$? – user74261 May 18 '15 at 18:13
  • The intersection of $\Omega^\circ$ and the convex segment $[p,y]$ is a convex set (another segment), and the map from $[p,y] \to [0,1]$ is linear, so this means that $I$ is a convex subset of $[0,1]$. (Continued...) – copper.hat May 18 '15 at 18:24
  • There is an open set around $y$ that does not intersect $\Omega^\circ$, and there is on open set around $p$ that does intersect $\Omega^\circ$, so $I$ must have the form $[0,t^*]$ or $[0,t^)$, for some $t^ \in (0,1)$. (Continued...) – copper.hat May 18 '15 at 18:26
  • Since $\Omega^\circ$ is open, $t^* \notin I$ (otherwise a quick contradiction). – copper.hat May 18 '15 at 18:28
  • To some extent, this is the most important part of the proof. – copper.hat May 18 '15 at 18:29
  • Thanks for explanation. appreciate it :) – user74261 May 18 '15 at 19:16
  • Hope it helped! – copper.hat May 18 '15 at 19:24
  • Why did you unaccept this answer after 5 years? – copper.hat Jun 17 '20 at 02:07
0

Here's another way to see it. Assume that $c$ and $p$ are distinct, otherwise the vector from $p$ to $c$ doesn't determine a particular hyperplane. You'd like to show that, for $x$ in $\Omega$,

$$(x - c)\cdot (c-p) \le 0.$$

Suppose not, and consider an $x$ in $\Omega$ for which $(x - c)\cdot (c-p) > 0.$ Take a positive $\varepsilon$ and consider the point $c_\varepsilon\equiv c + \varepsilon(c-x)$.

$$\begin{align}\|p-c_\varepsilon\|^2 &= \|p-c\|^2 + \varepsilon^2\|c-x\|^2 - 2\varepsilon (x-c)\cdot(c-p)\\ &< \|p-c\|^2, \end{align}$$ for $\varepsilon$ sufficiently small. Fix this small $\varepsilon$. Then $c_\varepsilon$ is strictly closer to $c$ than $p$. If a neighbourhood of $c_\varepsilon$ were in $\Omega$, then $c$ would be an interior point of $\Omega$. So we may take a point $d$ in a neighbourhood of $c_\varepsilon$ but outside $\Omega$ such that $\|d-p\|<\|c-p\|$. By a trivial topological argument, there is a boundary point of $\Omega$ in the line segment between $d$ and $p$. Such a boundary point is closer to $p$ than $d$ and hence also closer than $c$, contradicting the assumption that $c$ is the closest point on the boundary to $p$.

Interestingly, a small modification to the above argument shows that the same result holds for $p\notin\Omega$.

Ben Derrett
  • 4,592