# Farkas with strict inequalities

I have proven the following result. Let $a_i \in \mathbb{R}^n$ for $i = 1, \ldots, m$. Then precisely one of the following statements is true.

$$\text{(1) } c^t x < 0, \: a^t_i x \leq 0 \text{ has a solution } x \in \mathbb{R}^m$$

$$\text{(2) } \text{there exist } \mu_1 \geq 0, \ldots, \mu_m \geq 0, \text{ not all zero, such that } c + \sum_{i=1}^m \mu_i a_i = 0$$

Now I want to generalize this to the following statement

$$\text{(1) } c^t x < 0, \: a^t_i x < 0 \text{ has a solution } x \in \mathbb{R}^m$$

$$\text{(2) } \text{there exist } \mu_0 \geq 0, \ldots, \mu_m \geq 0, \text{ not all zero, such that } \mu_0c + \sum_{i=1}^m \mu_i a_i = 0$$

Now we could say that $a^t_i < 0$ iff we have an $\epsilon < 0$ such that $a^t_i - \epsilon \leq 0$ but I'm not sure how to use this.

• There are no $\mu_i$s in (2) ...... These two alternatives are equivalent if you add the assumption $\mu_0>0$ in the second item (2). – daw Oct 29 '15 at 18:51
• Ah yes sorry, I made a mistake. It should be fine now. – user119470 Oct 29 '15 at 19:14
• The item (2) of the second set of alternatives is always true (set all the $\mu$s to zero). – daw Oct 29 '15 at 20:17
• I should've been more precise. I should have added the condition that not all $\mu_i's$ are equal to zero. – user119470 Oct 30 '15 at 13:36

Assume that $$c^t x < 0, \: a^t_i x < 0$$ has no a solution $x \in \mathbb{R}^m$. Then for all $\epsilon>0$ the system $$c^t x < 0, \: (a_i- \epsilon c)^t x \le 0$$ has no a solution $x \in \mathbb{R}^m$. This implies that there $\mu_i^\epsilon\ge 0$ such that $$c + \sum_{i} \mu^\epsilon_i (a_i- \epsilon c)=0.$$ Assume that there is a converging subsequence $\mu^{\epsilon_k}\to\bar \mu$. Then passing to the limit yields (2).
If there is no such subsequence, then $(\mu^\epsilon)$ is unbounded. Then we divide the equation above by $\|\mu^\epsilon\|$: $$\frac1{\|\mu^\epsilon\|}c + \sum_{i} \frac{\mu^\epsilon_i}{\|\mu^\epsilon\|} (a_i- \epsilon c)=0.$$ Passing to the limit for a subsequence gives (2) as well.