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

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

We will put the required proposition into the above form. $$\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \iff Ax\le b \implies a'^Tx\le b' \iff \begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge0 $$

Hans
  • 2.3k
  • 15
  • 30