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?
- $\begingroup$ To show parallel, suppose $\tilde{a} = t a + p$ where $p \bot a$. Pick $x \in A_1$ and note that $x+\lambda p \in A_1$ for all $\lambda$. What does this say about $p$? $\endgroup$copper.hat– copper.hat2015-10-15 15:22:37 +00:00Commented Oct 15, 2015 at 15:22
- $\begingroup$ @user3697176 I had forgotten the condition $\tilde{b}\ge tb$. I made an edit. $\endgroup$mgus– mgus2015-10-15 23:48:28 +00:00Commented Oct 15, 2015 at 23:48
- $\begingroup$ @copper.hat I suppose that $p$ should be zero vector in order the hyperplanes to be parallel but I am not sure I understand the procedure. Also, why $p\perp a$ preserves generality? Can you add some more details since I am new to this field? $\endgroup$mgus– mgus2015-10-16 00:03:29 +00:00Commented Oct 16, 2015 at 0:03
3 Answers
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}$.
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'\|}$.
- $\begingroup$ Please use MathJax to render the math thank you. $\endgroup$user577215664– user5772156642020-10-28 11:14:52 +00:00Commented Oct 28, 2020 at 11:14
Here is an alternative proof for the main claim.
Assume that $a$ is not parallel to $\tilde a$ and $x \in \mathbb{R}^n$. Using Steinitz exchange lemma, we can find vectors $v_1, \dots, v_{n-2} \in \mathbb{R}^n$ such that $\{a, \tilde a, v_1, \dots, v_{n-2}\}$ is a basis for $\mathbb{R}^n$. Consider the following system of equations, where $\epsilon > 0$ is a small constant:
\begin{gather} \begin{bmatrix} a^T\\ \tilde a^T\\ v_1^T\\ \dots\\ v_{n-2}^T \end{bmatrix}x = \begin{bmatrix} b\\ \tilde b + \epsilon\\ 0\\ \dots\\ 0 \end{bmatrix} \end{gather}
The matrix on the left can be inverted to get a solution for this system of equations. Such a solution will satisfy $ax \le b$ and $\tilde a x > \tilde b$.
