0
$\begingroup$

Suppose that $A$ is an $m\times n$ matrix, $D$ is a $p\times n$ matrix, $b$ is an $m$-vector, and $d$ is a $p$-vector. Prove that there does not exist $n$-vector $x$ satisfying

$Ax \geq b, Dx \leq d$

if and only if there exist $m$-vector $y$ and $p$-vector $w$ satisfying

$ y \le 0, w \ge 0,$

$ (A^T)y + (D^T)w = 0,$

$ (b^T)y + (d^T)w < 0.$

1 Answers 1

1

Note that $Ax \geq b$, $Dx \leq d$ is equivalent to $\left(\begin{matrix}-A \\D \end{matrix}\right)x \leq \left( \begin{matrix}-b\\d\end{matrix}\right).$ Farkas' Lemma tells you that this does not have a solution if and only if there is a vector $u \geq 0$ that satisfies $u^T \left(\begin{matrix}-A \\D \end{matrix}\right) = 0 \quad \text{and} \quad u^T \left( \begin{matrix}-b\\d\end{matrix}\right) < 0.$ Then write $u = \left( \matrix{ -y \\ w} \right)$.

  • 0
    I've never heard o$f $Farkas Lemma. Thanks for shedding some light on what area I should look up on.:)2012-03-06