# Proof of Supporting Hyperplane Theorem

On page 51 of $\textit{Convex Optimization}$ by Boyd and Vandenberghe, they prove the Supporting Hyperplane Theorem using the Separating Hyperplane Theorem. That is, they prove that for a nonempty convex set $C\subseteq\mathbb{R}^n$ and any $x_0\in\text{bd}C$, there exists a supporting hyperplane to $C$ at $x_0$, i.e., there is an $a\ne 0$ such that $C\subseteq \{x\vert a^Tx\le a^T x_0\}$.

They proceed by considering two cases: $\text{int}C\ne \emptyset$ and $\text{int}C=\emptyset$. In both cases, the authors provide very limited details, but I was able to get through the first case. For the second case, they say the following: "If the interior of $C$ is empty, then $C$ must lie in an affine set of dimension less than $n$, and any hyperplane containing that affine set contains $C$ and $x_0$, and is a (trivial) supporting hyperplane."

I am able to prove the first part of that statement that if the interior of $C$ is empty, then $C$ must lie in an affine set $A$ of dimension less than $n$. However, I don't understand the second half. Of course, if we have an affine set $A$ of (affine) dimension less than $n$ then there exists some halfspace $H=\{x\vert a^Tx\le b\}$, $a\ne 0$, $b\in\mathbb{R}$, containing $A$. Furthermore, since $H$ is closed, it also contains $x_0$. So we can find a halfspace such that $C\subseteq H$ and $x_0\in H$.

My question is why is the halfspace containing $A$ necessarily a supporting hyperplane of $C$ at $x_0$? I don't see any reason why $\textit{any}$ hyperplane containing that affine set goes through $x_0$, let alone satisfies $a^Tx\le a^T x_0$ for all $x\in C$.

## 1 Answer

Hint : In fact you can prove that $C$ lies in boundary of $H$ i.e.,

$$C \subseteq A \subseteq \{x\vert a^Tx= b\}$$

Then clearly $H$ supports $C$ at $x_0$ (even at any point of $C$)

• I actually did do this in my proof but I was up late and not thinking straight. Thanks for pointing it out! – Satana Jun 3 '17 at 21:35