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!

  • $\begingroup$ I hesitate to call these polyhedra, but that's a minor point. You basically have the answer. However, you're never going to show that $C\subset(H_1\cup H_2)$, because $C$ has points that are in neither $H_1$ nor $H_2$. You need to show instead that $C\subset\mathop{\text{conv}}(H_1\cup H_2)$, and then that will give you $C=\mathop{\text{conv}}(H_1\cup H_2)$. $\endgroup$ – Josephine Moeller May 26 '13 at 16:32
  • $\begingroup$ @JohnMoeller Whoops, that's what I meant. I don't really know where to start with the last part. $\endgroup$ – john.abraham May 26 '13 at 17:17

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?

  • $\begingroup$ Hmm, if this was in $\mathbb{R}^2$, $H_1$ and $H_2$ would be lines, so in that case $H'$ could not contain $H_1$ or $H_2$, because any line that's not parallel with $a^Tx$ will intersect with $a^Tx$ at some point. $\endgroup$ – john.abraham May 27 '13 at 13:47
  • $\begingroup$ Bingo. Now just generalize it. $\endgroup$ – Josephine Moeller May 27 '13 at 17:16
  • $\begingroup$ So if I define $C'=\{ b_1\leq (a')^Tx \leq b_2\}$ for $a' \neq a$, is the idea that this set cannot contain $H_1$ or $H_2$, and then C is the only option? $\endgroup$ – john.abraham May 28 '13 at 19:12
  • $\begingroup$ e.g. assume that $C$ is not a subset of $conv(H_1\cup H_2)$, then there is a set $C'\subset C$ which is a subset of $conv(H_1\cup H_2)$, but $C'$ must be like the $C'$ of the previous comment, and we have a contradiction. $\endgroup$ – john.abraham May 28 '13 at 19:17
  • $\begingroup$ That's the basic idea, yes. $\endgroup$ – Josephine Moeller May 29 '13 at 1:00

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.