0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.