4
$\begingroup$

Consider the following Theorem of Alternatives:

Let $A \in \mathbb{R}^{n}, b \in \mathbb{R}^{m}.$ Then exactly one of the following statements is true:

(1) $\exists x \in \mathbb{R}^{n} : Ax \leq b$

(2) $\exists p \in \mathbb{R}^{m} : p \geq 0, p^TA = 0, p^Tb < 0.$

Also, Consider Farkas Lemma:

(1) $\exists x \in \mathbb{R}^{n} : Ax = b, x \geq 0$

(2) $\exists p \in \mathbb{R}^{m} : p^TA \geq 0^T, p^Tb < 0.$

Prove Farkas Lemma using the Theorem of Alternatives.

Note: It is possible, and potentially much easier, to prove Farkas Lemma using strong and weak duality, but I am looking for a proof that takes advantage of the Theorem of Alternatives, rather than the duality of Linear Programs.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

To prove Farkas' lemma, we must show $\neg (1)\Leftrightarrow (2)$.

[$\neg (1)\Rightarrow (2)$] Note that the system $Ax=b,x\geq 0$ can be written as

$$\begin{bmatrix}A\\-A\\I\end{bmatrix}x\leq\begin{bmatrix}b\\-b\\0\end{bmatrix}.$$

This system is in the form given in the first theorem of the alternative (TOA). Thus, by that TOA, $\exists\ p_1,p_2,p_3\in\mathbb{R}^m_+$ such that

$$(p_1-p_2)^\text{T}A = p_3^\text{T} \quad\text{and}\quad (p_1-p_2)^\text{T}b<0$$

Take $p:=p_1-p_2$ and use that $p_3\geq 0$ to conclude.

[$(2)\Rightarrow\neg(1)$] Suppose (2), and for contradiction suppose (1) as well. Then $p^\text{T}A\geq0^\text{T}$ and $x\geq 0$ imply $p^\text{T}Ax\geq 0$. But $Ax=b$ implies $p^\text{T}Ax=p^\text{T}b\geq 0$, which is a contradiction.

$\endgroup$
3
  • 1
    $\begingroup$ Please fix your typo in the last line thanks $\endgroup$
    – xk3
    Commented Apr 28, 2017 at 20:44
  • $\begingroup$ @David M.: Can we prove the Theorem of Alternatives (the first set of conditions) from Farkas lemma above ? $\endgroup$
    – me10240
    Commented Jan 14, 2019 at 4:53
  • $\begingroup$ @me10240 Yes I think so. You should be able to do a similar transformation, but in the opposite direction. $\endgroup$
    – David M.
    Commented Jan 14, 2019 at 12:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .