[Math] Prove the supporting hyperplane theorem for convex sets in Euclidean spaces

convex optimizationconvex-analysisconvex-geometryfunctional-analysis

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.

Best Answer

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