Proving a projection based on Farkas Lemma

Question

In an Integer Programming book, a proof is given for a theorem but i do not understand a certain step:

Theorem: Consider a polyhedron $P := \{(x,z) \in R^n \times R^p: Ax+Bz\leq b\}$ and let $r^1$,...,$r^q$ be the extreme rays of $C_p$: the cone of $P$. Then, $proj_x(P) = \{x \in R^n: r^tAx \leq r^t \forall t = 1,...,q\}$

Proof: It suffices to show that for any $x$, $ x \notin proj_x(P) $ if and only if $r^tAx>r^tb$ for some $t = 1,...,q$. By definition $ x \notin proj_x(P) $ if and only if the system $Bz <b-Ax$ is infeasible.

I get it until here

Proof (cont): By Farkas Lemma, the latter system is infeasible if and only if there exists a vector $u \in C_p$ such that $uAx \geq ub$

Here is where i am lost. How do they come to this based on Farkas Lemma?

Farkas lemma: Given matrix $A$ and vector $b$, exactly one of the following statements is true:

1. $\exists x$ such that $Ax=b$ and $x \geq 0$
2. $\exists y$ such that $y^TA \geq 0^T$ and $y^Tb < 0$

Definition Cone: The cone of $P=\{(x,z) \in R^n \times R^p: Ax +Bz \leq b\}$ is $C_P = \{u \in R^m: uB=0, u \geq 0\}$

Answer 1

$x\notin\mathrm{proj}_x(P)$ if and only if the system $Bz\leq b-Ax$ is infeasible.

The statement you want follows from one of the generalized forms of Farkas' lemma. In particular Theorem 3.6 in "Integer Programming" by Conforti et al says that exactly one of these holds:

• $\exists y$ such that $By\leq f$
• $\exists u$ such that $uf< 0$ and $uB=0,$ $u\geq 0$

Substituting in $z$ and $b-Ax$ for $y$ and $f$ gives what you want.

---

To prove the generalization from the basic version of Farkas' lemma, add slack variables $w$ to convert the system to an equality, and split $y$ into positive and negative parts:

$$\exists y^+,y^-,w\text{ such that }By-By+w=f\text{ and }y^+,y^-,w\geq 0$$ or in block matrix form: $$\exists y^+,y^-,w\text{ such that }\begin{pmatrix}B&-B&I\end{pmatrix}\begin{pmatrix}y^+\\y^-\\w\end{pmatrix}=f\text{ and }y,y',w\geq 0$$

By Farkas' lemma this system is infeasible if and only if: $$\exists u\text{ such that }u\begin{pmatrix}B&-B&I\end{pmatrix}\geq 0\text{ and }uf<0$$ i.e. $$\exists u\text{ such that }uB=0\text{ and }u\geq 0\text{ and }uf<0.$$