[Math] Determining the convex hull of the union of two polyhedra

convex-analysislinear programming

I'm doing an introductory course to linear programming and I'm working through some exercises to prepare for the final exam, I'm stuck on an exercise and I would really appreciate a hint:

Let $a\in \mathbb{R}^n $ where $\Vert a\Vert = \sqrt{a^T a}=1\,$ and let$\,\,b_1 , b_2 \in \mathbb{R}$ with $b_1 < b_2$. Define $H_1=\{ x\in \mathbb{R}^n : a^Tx=b_1\}$ and $H_2=\{ x\in \mathbb{R}^n : a^Tx=b_2\}$

Determine the convex hull of $H_1 \cup H_2$

The first thing I would do here is to define $C=\{ x\in \mathbb{R}^n : b_1 \leq a^Tx \leq b_2\}$, which is a polyhedron and therefore convex, and so $conv( H_1 \cup H_2) \subset C$.

$conv(S)$ here means the intersection of all convex sets that contain $S$.

I just need to show that $C \subset conv( H_1 \cup H_2)$, but I don't really know where to start.

Thanks in advance!

Best Answer

Hint: $H_1$ and $H_2$ are hyperplanes, so what happens if you take any old halfspace $H'= \{x \mid (a')^T x \leq c \}$ for $a\neq a'$? Does $H'$ contain $H_1$ or $H_2$? Why or why not?

Related Question