# Prove the supporting hyperplane theorem for convex sets in Euclidean spaces

Let $A\subset \Bbb R^n$ be convex and $p\in\partial A\ne \varnothing$, prove that $\exists v\in\Bbb R^n$ such that $$v^T(x-p)\ge 0,\quad \forall x\in A.$$ Note that the separation may not be strict (say, if $A$ is itself a hyperplane etc).

Since $\text{int}\, A$ and $p$ are disjoint and convex, there exists $v\in\Bbb R^n$ such that $v^T(x-p)>0,\,\forall x\in\text{int}\, A$. Now the major task is to pass this result to $A$ and $p$.

Indeed I only need to show that each point in $A$ can be approximated by points in its interior. However this may not be true, since $A$ may have empty interior. Even if $A$ has nonempty interior, it's not immediately clear why points $A$ can be approximated by its interior points, though geometrically it seems obvious.

So now there are two major problems:
1). When $A$ has empty interior, then $A$ must lie in a hyperplane. In other words, $A$ has affiné dimension less than $n$. (This would be clearly false in infinite dimensional spaces, say $A$ is the range of an injective compact operator. So I guess the finite dimensionality has a key role to play here.)
2). If $A$ has nonempty interior, then any point in $A$ can be approximated by points in its interior.

Looking forward to any help. Cheers.

EDIT
Just a little caveat: you might be very tempted to use, perhaps implicitly, some "advanced" properties of convex sets like "any convex set in $\Bbb R^n$ is the intersection of affine sets". But this may lead to circular reasoning, because, for instance, the proof of the property mentioned just above is, AFAIK, based exactly on the supporting hyperplane theorem which we want to prove here.

First, since the set $$A$$ is convex, the point $$p\in\partial A$$ also belongs to $$\partial\overline A$$.

Next, take a sequence of $$p_n\to p$$ where $$p_n\notin\overline A$$, and consider the following minimization problem: $$\Vert x-p_n\Vert^2\equiv(x-p_n)^T(x-p_n)\to\min_{x\in\overline A}.$$ Since $$\overline A$$ is a closed convex set, and the objective function tends to infinity when $$x$$ goes to infinity, there exists a solution $$x_n$$. And since $$p_n\notin\overline A$$, we have $$\Vert x_n-p_n\Vert>0$$

Next, consider the $$v_n=x_n-p_n$$. One can show that $$v_n^T(x-p_n)>0$$ for any $$x\in\overline A$$. Indeed, if there existed $$x\in\overline A$$ such that $$v_n^T(x-p_n)\le0$$ then we could consider vectors $$x_\lambda=(1-\lambda)x_n+\lambda x)\in\overline A$$ for a small positive $$\lambda$$, and for it $$\Vert x_\lambda-p_n\Vert^2=\Vert (1-\lambda)(x_n-p_n)+\lambda(x-p_n)\Vert^2 =(1-\lambda)^2\Vert x_n-p_n\Vert^2+2\lambda(1-\lambda)(x_n-p_n)^T(x-p_n)+\lambda^2\Vert x-p_n\Vert^2<\Vert x_n-p_n\Vert^2$$ which contradicts the fact than $$x_n$$ is a minimum point for the problem above.

Next, consider the sequence of $$v_n'=\dfrac{v_n}{\Vert v_n\Vert}$$. They all belong to the unit sphere which is a compact in $$\mathbb R^n$$, so there exists a converging subsequence $$v_{n_k}'$$ of them. Since for all $$v_n'$$ we also have $$v_n'^T(x-p_n)>0$$ for any $$x\in\overline A$$ then for the limits $$v=\lim_{k\to\infty}v_{n_k}'$$ and $$p=\lim_{k\to\infty}p_{n_k}$$ the inequality also holds (possibly as an equality): $$v^T(x-p)\ge0$$for all $$x\in\overline A$$ (and so for all $$x\in A$$).

• Could you elaborate on why $\partial A\subset \partial \bar A$, given $A$ convex? – Vim Jan 14 '17 at 9:16
• Also, how do you know you can always take $p_n\to p$ with $p_n\notin \bar A$? For generic sets this is not always possible, say $A=\Bbb Q^n$. Of course I know convexity is too good a property to allow for such irregularities, but I still do not have any idea how to prove, with mathematical rigour, that such a sequence always exists. (I have some intuition about the geometry of convex sets, but admittedly very little rigorous formalism of it.) – Vim Jan 14 '17 at 9:27
• @Vim: I'll edit the answer a bit later regarding the first statement. As for the existence of $p_n$, it follows from the closeness of $\overline A$. – Sergei Golovan Jan 14 '17 at 9:41
• thanks. I just searched the site a little and found the following property (not easy to prove, though): if $A$ is convex then $\text{int}\, A=\text{int}\,\bar A$, which can answer both my first and my second questions. – Vim Jan 14 '17 at 9:53
• You're right, it's easier to prove that $int A=int\overline A$ (for convex $A\in\mathbb R^n$) then do that for the boundaries directly. And there was a few question on this asked before. This one's answer is which I'd like the most. – Sergei Golovan Jan 15 '17 at 6:47