When is a halfspace a subset of another halfspace?

Question

Let's say we have the following halfspaces:$$H_1=\left \{x\mid a^tx\leq b\right \}$$and$$H_2=\left \{x\mid \tilde a^tx\leq \tilde b\right \}.$$I want to find the conditions that need to hold such that $H_1\subseteq H_2$. So these halfspaces are defined by the hyperplanes, say,$$A_1=\left \{x\mid a^tx=b\right \}$$and$$A_2=\left \{x\mid \tilde a^tx=\tilde b\right \}.$$Intuitively I understand that $H_1\subseteq H_2$ demands the hyperplanes to be parallel or equivalently the normal vectors $a$ and $\tilde a$ to be parallel, so:\begin{align*}A_1\parallel A_2 & \iff a\parallel \tilde a \\ & \iff \exists t\in \mathbb{R}\text{ such that }\tilde a=ta. \end{align*}The hypothesis $H_1\subseteq H_2$ also requires the $H_2$ to lie above $H_1$ which restricts us to consider $\tilde b\geq tb$ for positive values of $t$ ($t>0$). But how can I formally prove that these two conditions are enough and necessary?

Answer 1

Sorry for reviving this old thread. I think well-known questions like this one must have an answer.

Suppose that $H_1 \subseteq H_2$, then the following must be true:

Claim 1. $\bar{a}$ and $a$ are parallel, i.e there exist $k \in \mathbb{R}$ such that $k \neq 0$ and $\bar{a} = ka$.

Proof: Suppose there is no $k \in \mathbb{R}$ such that $\bar{a} = ka$, then $\bar{a}$ and $a$ must be linearly independent, hence there is $x_0 \in \mathbb{R}^n$ such that $a^Tx_0 = b$ and $\bar{a}^Tx_0 = \bar{b}$. Now let $a^{\perp} \in \mathbb{R}^n$ be the orthogonal complement of $a$, i.e $a^T \cdot a^{\perp} = 0$. Consider vectors of the form $v_t = x_0 + ta^{\perp}$. Clearly $$a^Tv_t = a^T(x_0 + ta^{\perp}) = b \implies v_t \in H_1.$$ On the other hand, $$\bar{a}^Tv_t = \bar{a}^Tx_0 + t(\bar{a}^T \cdot a^{\perp}) = \bar{b} + t(\bar{a}^T \cdot a^{\perp})$$ Note that $\bar{a}^T \cdot a^{\perp} \neq 0$, otherwise $a$ and $\bar{a}$ must be parallel. So, we can choose $t$ as $1$ or $-1$ such that $\bar{a}^Tv_t > \bar{b}$.

Claim 2. $k$ we found in claim 1 must be positive.

Proof: If $k$ is negative, then $$H_2 = \{x \mid \bar{a}^Tx \leq \bar{b}\} = \{x \mid ka^Tx \leq \bar{b}\} = \{x \mid a^Tx \geq \frac{\bar{b}}{k}\}$$ Clearly, $H_1$ can't be contained in $H_2$ since the inequality sign is different.

Claim 3. $kb \leq \bar{b}$.

Proof: Note that $$H_2 = \{x \mid \bar{a}^Tx \leq \bar{b}\} = \{x \mid ka^Tx \leq \bar{b}\} = \{x \mid a^Tx \leq \frac{\bar{b}}{k}\}$$

For $H_1 = \{x \mid a^Tx \leq b\}$ to be contained in $H_2$, clearly $b \leq \frac{\bar{b}}{k}$. Hence $kb \leq \bar{b}$.

Therefore, the necessary and sufficient condition is that there exists $k > 0$ such that $\bar{a} = ka$ and $kb \leq \bar{b}$.

Answer 2

For the general case, to appear $t> 0$, let us normalize the vectors $a, b$. Then we have, $H_1=\{x\mid a^Tx \le b\} = \{x\mid\frac{a^T}{\|a\|} \le \frac{b}{\|a\|}\}$. Do the same for $H_2$ and do the same as above. We will show $t =\frac{\|a\|}{\|a'\|}$.