Skip to main content
1 of 4
Hans
  • 2.3k
  • 15
  • 30

Confining a polytope to one side of an affine hyperplane

This answer claims the following proposition.

Using Farkas' lemma to show, a halfspace $\{x \mid a' x \leq b' \}$ contains the polytope $P= \{x |A x \leq b \}$ if and only if there exists $\lambda \in \mathbb{R}^m$ with $\lambda \geq 0$ (understood component-wise) such that: \begin{align*} a' &= \lambda^T A \\ b' &\geq \lambda^T b \end{align*}

It is easy to prove the sufficiency. I am able to show the necessity of $a' = \lambda^T A$ by Farkas' lemma, but not $b' \geq \lambda^T b$. I tried but failed to argue by contradiction. How does one prove that last inequality?

Hans
  • 2.3k
  • 15
  • 30