0

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.

user119470
  • 59
  • 7
  • 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

1 Answers1

0

Let me prove that the second set of alternatives follows from the first. Obviously not both systems can have solutions.

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.

daw
  • 49,113
  • 2
  • 38
  • 76