The Farkas Lemma: Let $A$ be an $m\times n$ matrix, $b\in\mathcal{R}^m$. Then exactly one of the following two assertions is true:
(1) There exists an $x\in \mathcal{R}^n$ such that $Ax=b$ and $x\ge0$.
(2) There exists a $y\in \mathcal{R}^m$ such that $A^Ty\ge0$ and $b^Ty<0$.
I want to check which assertion is true for a given $b$. So I constructed the linear programming problem according to the second statement:
\begin{equation}
\min b^Ty\\
s.t. -A^Ty\le0
\end{equation}
The idea is simple. if the solution $b^Ty$ is great than or equal to $0$, then the first assertion is true; otherwise the second one is true.
But the following matlab implementation always gives me the result $y=0$ or "the problem is unbounded". Something is wrong, but i have no idea. I would be thankful for any help or references.
m = 2;
n = 4;
A = rand(m,n);
b = rand(m,1);
f = b;
A = -A';
y = linprog(f,A,zeros(n,1),[],[],[],[]);
Best Answer
Suppose you found a $y$ such that $-A^Ty \le 0$ and $b^Ty < 0$. Notice that $ky$, where $k$ is positive, would also be feasible and hence we can scale $y$ to arbitary large magnitude, hence $\min b^Ty$ doesn't exists and it can go to $-\infty$, it is unbounded.
You might like to impose the constraint $b^Ty \ge -1$ so that you do not get the unbounded message.