0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – daw Oct 29 '15 at 18:51
  • $\begingroup$ Ah yes sorry, I made a mistake. It should be fine now. $\endgroup$ – user119470 Oct 29 '15 at 19:14
  • $\begingroup$ The item (2) of the second set of alternatives is always true (set all the $\mu$s to zero). $\endgroup$ – daw Oct 29 '15 at 20:17
  • $\begingroup$ I should've been more precise. I should have added the condition that not all $\mu_i's$ are equal to zero. $\endgroup$ – user119470 Oct 30 '15 at 13:36
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.