Let $A$ be an $m$x$n$ matrix, $B$ $l$x$n$ matrix and $c\in R^n$. Prove that exactly one of the systems has a solution:

i)$$Ax\leq0,\:\: Bx=0,\:\: c^Tx>0,\:\: x\in R^n$$ ii)$$A^Tp+B^Tq=c,\:\:p\geq0,\:\:p\in R^m,\:\:q\in R^l$$

It's easy to prove that neither can be true at the same time by simply transposing and multiplying by x ii) and the other way around, but how do I show that exactly one must be true?

The hint which does not make much sense to me is to take $q=r-s$ where $r,s\geq0$.

  • 1
    $\begingroup$ The hint allows you to only have nonnegative variables in problem (ii) and be exactly in the situation of Farkas' lemma. $\endgroup$ – Michal Adamaszek Dec 13 '19 at 12:50

Suppose $(ii)$ has a solution, then $(i)$ can't have a solution.

Now suppose $(ii)$ doesn't have a solution, then the following problem is not feasible:

$$\min 0$$ $$A^Tp + B^Tr-B^Ts = c$$ $$p \ge 0$$ $$r \ge 0$$ $$s \ge 0$$

Let's consider it's dual.

$$\max c^Tx$$ $$Ax \le 0$$ $$Bx \le 0$$ $$-Bx \le 0$$

Check that it is feasible and conclude that it is unbounded and that should help you to conclude that $(i)$ has a solution.


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.