0
$\begingroup$

The proof of Farka's lemma is known.

An important corollary of Farkas lemma is stated as
Modified Farkas Lemma. Let $A$ be an $m\times n$ matrix with values in $R$ and $b\in R^m$. Then exactly one of the following holds

  1. $\exists x\in R^n$ such that $Ax\le b$
  2. $\exists y\in R^m,y\ge0$ such that $A^Ty=0,y^Tb<0$.

Attempt. Verification that both do not hold together is trivial. Suppose 2 does not hold. Then, $\not\exists y\ge0,y\in R^m$ such that $A^Ty=0,y^Tb<0$. We need to show that 1 necessarily holds.

Construct $\hat A_{(n+1)\times m}=\begin{pmatrix}A^T\\b^T\end{pmatrix},\hat b_{(n+1)\times 1}=\begin{pmatrix}0\\\vdots\\0\\-1\end{pmatrix}$. Applying Farkas lemma on this, we get

  • $\exists z\ge 0,z\in R^m$ such that $\hat Az=\hat b$, or
  • $\exists w\in R^{n+1}$ such that $\hat A^T w\ge0,w^T\hat b<0$

The first implies that $\exists z\in R^m,z\ge0$ such that $A^Tz=0,b^Tz=-1<0$ which is a contradiction since 2 does not hold. Hence, $\exists w\in R^{n+1}$ such that $\hat A^T w\ge0,w^T\hat b<0$.

How do I proceed from here?

$\endgroup$

1 Answer 1

0
$\begingroup$

We have $\exists w\in R^{n+1}$ such that $\hat A^Tw\ge\boldsymbol{0}$ and $w^T\hat b<0$. Since, $w\in R^{n+1}$ we write it in the form $$w=\pmatrix{w_0\\\lambda},\quad w_0\in R^n,\lambda\in R.$$ We get $$\pmatrix{A,b}\pmatrix{w_0\\\lambda}\ge0\Rightarrow Aw_0+\lambda b\ge0\quad\text{and}\quad\pmatrix{w_0,\lambda}\pmatrix{\boldsymbol{0}\\-1}<0\Rightarrow\lambda>0\\\Rightarrow A\left(\frac{-1}{\lambda}w_0\right)\le b$$

Taking $x=\frac{-1}{\lambda}w_0$, we get that $\exists x\in R^{n}$ such that $Ax\le b$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .