2
$\begingroup$

I'm trying to understand the analytic proof of Farkas lemma (presented in a lecture) but I may have noted some steps wrong.

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=b,x\ge0$
  2. $\exists y\in R^m$ such that $A^Ty\ge0,y^Tb<0$.

Proof. The verification that both cannot hold together is straightforward. Proof that one statement must hold is, as follows.

Let $v_1,v_2,...v_n$ be column vectors of $A$ and let $Q=\{s\in R^m:s=\sum_{i=1}^n\lambda_iv_i,\lambda_i\ge0\forall i\}$. Suppose condition 1 doesn't hold, then we must show that 2 necessarily holds.
1 does not hold $\Rightarrow\nexists x$ such that $Ax=b\Rightarrow b\notin Q$. Also, $0\in Q\Rightarrow Q\ne\emptyset$.

I do not understand the steps below.

By separating hyperplane theorem (disjoint convex sets can be separated by a hyperplane) $\exists \alpha\in R^m,\alpha\ne0$ and $\beta$ such that $$\alpha^Tb>\beta~\text{ and }~\alpha^Ts<\beta\forall s\in Q\tag{$*$}$$ Also, $\forall \gamma>0$, $\gamma v_i\in Q$. Since $0\in Q$, $\beta>0$. $$\alpha^T(\gamma v_i)<\beta\forall\gamma>0\Rightarrow\alpha^T v_i<\frac{\beta}{\gamma}\Rightarrow\alpha^T v_i\ge0$$ Now, consider $-\alpha=y\Rightarrow y^TA\ge0$. From $(*)$, $$\alpha^Tb>\beta>0\Rightarrow y^Tb<0$$

UPDATE. Found a visualization of the proof here.

$\endgroup$
2
  • $\begingroup$ Can you be more specific about what parts you don't understand? Do you understand the separating hyperplane theorem? Do you see how it gives you (*)? $\endgroup$ Apr 4 at 14:53
  • $\begingroup$ @RobertIsrael I don't see how it gives the subsequent result. Also, fail to understand why $\beta>0$ and the next equation. $\endgroup$
    – reyna
    Apr 4 at 15:15

1 Answer 1

1
$\begingroup$

By separating hyperplane theorem, we can find such a hyperplane that separates disjoint convex set. Our disjoint convex set is the point $\{b\}$ and $Q$ since we assume that $[1]$ doesn't hold.

The hyperplane can be written as $\alpha^Tx=\beta$ where $\alpha \ne 0$. The point $\{b\}$ and $Q$ lies on different sides of the hyperplane.

Hence, we can say that $\alpha^Tb > \beta$ and $\alpha^Ts < \beta, \forall s \in Q$.


Now, recall that we have $0 \in Q$, and since $\alpha^Ts < \beta, \forall s \in Q$, if we choose the particular $s$ to be $0$, then we have $\alpha^T0 < \beta$, hence we have $\beta>0$.


Now, if $\gamma>0$, we have $\gamma v_i \in Q$

$\alpha^T(\gamma v_i) < \beta, \forall \gamma >0$, hence we have $\alpha^Tv_i <\frac{\beta}{\gamma}, \forall \gamma>0$

There is a typo in the next line of reasoning.

Hence, by letting $\gamma$ to be arbitrarily large, the right conclusion should be $\alpha^Tv_i \color{red}\le 0$.


Now, we let $y=-\alpha$, then we have $-y^Tv_i \le 0$ or $y^TA \ge 0$.

From $\alpha^Tb > \beta>0$, we have $-y^Tb > 0$ or $y^Tb<0$.

$\endgroup$

You must log in to answer this question.

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