2
$\begingroup$

S is the polyhedral set

$ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $

and

$ H : \mathbf{c}^{T}\mathbf{x} = \beta $

with

$ \min_S ( \mathbf{c}^{T}\mathbf{x} )= \beta $

My textbook states that given the above, the set $S \cap H$ contains no line since $\mathbf{x} \ge \mathbf{0}$ in $S$. But I don't understand why.

1 Answers 1

3

Any line in $\mathbb R^2$ can be written as $L = \left\{ \left(\begin{matrix}x \\ y\end{matrix}\right) + t \left(\begin{matrix}u \\ v\end{matrix}\right) : t \in \mathbb R \right\}$ where $u$ and $v$ are not both zero. For some choice of $t$, either $x+tu < 0$ or $y + tv < 0$. So $L$ contains a point $\mathbf x$ that does not satisfy $\mathbf x \geq 0$. So $L$ cannot be contained in $S$ (and hence not in $S\cap H$, no matter what $H$ is).

  • 0
    Yes, it works just the same in $\mathbb R^n$.2012-11-25