# Linear Programming Duality (Basic optimization)

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.$$

-

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)$.