0
$\begingroup$

In wikipedia, Farkas' lemma is as follows:

Let $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^n$. Then exactly one of the following statement is true:

  1. There exists $Y \in \mathbb{R}^n$ such that $AY = b$ and $Y\ge 0$.
  2. There exists $X \in \mathbb{R}^m$ such that $A^TX \ge 0$ and $b^TX \le 0$.

I am reading about linear separation here. In the last paragraph on page 2, it said that

Then, by Farkas’ lemma, if (3) is not feasible, i.e. if there does not exist $X$ such that $AX\ge U$, then there exists $Y$ such that $Y^TA = 0$, $Y^TU > 0$ and $Y\ge0$.

Below is equation (3): \begin{align*} \begin{cases} \langle a, x_i \rangle + b \ge 1&\text{if }y_i = 1\\ \langle a, x_i \rangle + b \le -1&\text{if }y_i = -1 \end{cases} \end{align*} Let $I = \{i| y_i = 1\}$ and $J = \{j| y_j = - 1\}$. In the matrix form, linear inequalities of (3) is equivalent to $AX \ge U$, where $A$ is $p \times (n+1)$ matrix whose $k-$th row is $[x_k^T\ 1]$ if $k \in I$ and $[-x_k^T\ -1]$ if $k \in J$, X is the concatenation of $a \in \mathbb{R}^n$ and $b\in \mathbb{R}$, and $U \in \mathbb{R}^p$, whose entries are all ones.

I do not get how "there does not exist $X$ such that $AX\ge U$" implies "there exists $Y$ such that $Y^TA = 0$, $Y^TU > 0$ and $Y\ge0$". Particularly, I do not understand how they get $Y^TA = 0$.

Note: I switched A and X in the second quoted paragraph above so that it corresponds with Farkas' Lemma.

$\endgroup$
2
  • $\begingroup$ Your version of Farkas' lemma is wrong. When $b=0$, both statements are trivially true simultaneously. $\endgroup$
    – LinAlg
    Apr 23, 2018 at 15:08
  • $\begingroup$ Alright. I am aware of the fact that there are a few different versions of Farkas' Lemma. Which version do you think will apply the best here? $\endgroup$
    – abuchay
    Apr 23, 2018 at 15:11

1 Answer 1

0
$\begingroup$

Take the generalized Farkas' lemma with a cone $C$ and its dual cone $C^*$:

  1. There exists $x \in \mathbb{R}^n$ such that $Ax = b$ and $x \in C$.
  2. There exists $y \in \mathbb{R}^m$ such that $A^T y \in C^*$ and $b^Ty < 0$.

Your $Ax \geq b$ falls in the first case by adding a slack variable: $Ax - s = b$, with $(x,s) \in C$ and $C = \mathbb{R}^{n+1} \times \mathbb{R}^k_+$. Since $C^*=\{0\}^{n+1} \times \mathbb{R}^k_+$, the second statement is: there exists $y \in \mathbb{R}^k$ such that $A^Ty=0$, $-y\geq 0$, $b^Ty<0$.

$\endgroup$
2
  • $\begingroup$ How did you get $A^Ty = 0$? Also in my question, $b$ is a matrix whose entries are all ones so $b^T y <0$ does not make quite sense to me given that $y \ge 0$. $\endgroup$
    – abuchay
    Apr 23, 2018 at 22:38
  • $\begingroup$ The $A$ in the lemma is actually $[A \; -I]$, so $A^Ty=0$ and $-y \geq 0$ follow from $A^T y \in C^*$. $\endgroup$
    – LinAlg
    Apr 23, 2018 at 23:18

You must log in to answer this question.

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