How to show that exactly one of the following inequality systems has a solution?

118 Views Asked by At

This is from a homework set of my optimization class.

Let $A \in \mathbb{R}^{m \times n}$. Show that exactly one of the following inequality systems has a solution: $$ \mathbf{I}: \,\,\,Ax \leq 0, \,\,\,\,x\geq 0, \,\,\,\ \sum_{i=1}^{n}x_i=1 $$ $$ \mathbf{II}: \,\,\,A^Ty > 0, \,\,\,\,y\geq 0, \,\,\,\ \sum_{i=1}^{m}y_i=1 $$


We cannot apply Farka's Lemma directly because the first problem in Farkas lemma is equality:

$$ \textbf{I}: \,\,\,Ax =b, \,\,\,\,x\geq 0 $$

$$ \textbf{II}: \,\,\,A^Ty \leq 0, \,\,\,\,b^Ty> 0 $$