Help fit a similar claim into Farka's lemma.

Question

I found the following implication of Farka's lemma in Wikipedia,

If $Ax \le b$ has not solution, then there exists $y$ such that $y^TA=0,y^T=-1$.

The claim we want to show is similar but a little bit different (see "previously asked" below for more).

If system $A_1x \ge 0, ..., A_Nx \ge 0, f^Tx=1$ has no solution,then there exists vectors $y_1,...,y_N$ and a real number $\mu > 0$ s.t. $y_1^TA_1+...+y_N^TA_N+\mu f=0$

I have trouble to completely fit this claim to above implication of Farka's lemma. Please help.

---

Previously asked:

See the following. Can anyone help point out what version of Farka's lemma this is using?

---

I check my textbook and find all mention of Farka's lemma but I have trouble to match them with the claim in the proof.

Answer 1

The last picture "Proposition 5.1.2 (b)" is exactly for your problem. It states an "if and only if" condition for the existence of solution, and we can derive the negation (the negation of proposition $p \to q$ is $p\wedge \neg q$):

The system $Ay\ge c$ has no solution if and only if there exists some $x$ such that $A^Tx=0,x\ge0$ and $c^Tx>0$.

Or equivalently,

The system $Ax\ge b$ has no solution if and only if there exists a linear combination $y$ such that $y^TA=0,y\ge0$ and $y^Tb>0$.

Let's rewrite $A_1x \ge 0, ..., A_Nx \ge 0, f^Tx=1$ in a single system as ${\left( {\begin{array}{*{20}{c}} {{A_1}} \\ \vdots \\ {{A_N}} \\ {{f^T}} \\ { - {f^T}} \end{array}} \right)_.}x \geqslant {\left( {\begin{array}{*{20}{c}} 0 \\ \vdots \\ 0 \\ 1 \\ { - 1} \end{array}} \right)_.}$

It has no solution, meaning there exists a linear combination $y$ such that

${y^T}{\left( {\begin{array}{*{20}{c}} {{A_1}} \\ \vdots \\ {{A_N}} \\ {{f^T}} \\ { - {f^T}} \end{array}} \right)_.} = 0,y \geqslant 0,{y^T}{\left( {\begin{array}{*{20}{c}} 0 \\ \vdots \\ 0 \\ 1 \\ { - 1} \end{array}} \right)_.} > 0$

This easily leads to (11) in your problem by letting $\mu$ be the subtraction of the last two components of $y$, and letting $\lambda_{ip}$ be other components of $y$. Q.E.D.