To prove this version of Farkas' Lemma using the separating hyperplane theorem, let's restate the lemma clearly:

Farkas' Lemma:

Let $A \in \mathbb{R}^{M \times N}$ and $b \in \mathbb{R}^M$. Exactly one of the following two statements is true:

1. There exists a vector $x \in \mathbb{R}^N_+$ (meaning $x \geq 0$ component-wise) such that $Ax = b$.
2. There exists a vector $\lambda \in \mathbb{R}^M$ such that $A^T \lambda \leq 0$ (component-wise), and $\lambda^T b > 0$.

Proof:

1. Assume (1) is true:

   • There exists $x \geq 0$ such that $Ax = b$.
   • Now, assume for contradiction that (2) also holds.
   • This means there exists $\lambda \in \mathbb{R}^M$ such that $A^T \lambda \leq 0$ and $\lambda^T b > 0$.
   • Consider the expression $\lambda^T b = \lambda^T A x$.
   • Since $\lambda^T A \leq 0$ and $x \geq 0$, it follows that $\lambda^T A x \leq 0$.
   • However, we assumed that $\lambda^T b > 0$, which contradicts $\lambda^T b = \lambda^T A x \leq 0$.
   • Therefore, if (1) is true, (2) cannot be true.

2. Assume (1) is false:

   • This means there is no $x \geq 0$ such that $Ax = b$.
   • Let $C = \{Ax : x \geq 0\} \subset \mathbb{R}^M$. This set $C$ is a convex cone.
   • Since $b \notin C$, by the separating hyperplane theorem, there exists a nonzero vector $\lambda \in \mathbb{R}^M$ and a scalar $\gamma$ such that: $\lambda^T y \leq \gamma \quad \text{for all } y \in C,$ $\lambda^T b > \gamma.$
   • Since $C$ is a cone (closed under non-negative scalar multiplication), the inequality for all $y \in C$ implies $\gamma$ must be non-positive (i.e., $\gamma \leq 0$).
   • If $\gamma < 0$, then for any $x \geq 0$, we would have $\lambda^T A x \leq \gamma < 0$, contradicting the existence of any $x \geq 0$ such that $Ax = b$.
   • Hence, $\gamma = 0$ and thus $\lambda^T A x \leq 0$ for all $x \geq 0$. This means $A^T \lambda \leq 0$.
   • Moreover, since $\lambda^T b > \gamma = 0$, it follows that $\lambda^T b > 0$.
   • Therefore, (2) must hold if (1) does not.

This completes the proof of Farkas' Lemma: either (1) or (2) holds, but not both simultaneously.

Would you like to delve into any aspect of this proof further or have any questions?

Related Questions

1. How does the separating hyperplane theorem apply to the proof of Farkas' Lemma?
2. Can you provide an example illustrating Farkas' Lemma in practice?
3. What is the significance of the condition $\lambda^T b > 0$ in the lemma?
4. How is Farkas' Lemma used in duality theory in linear programming?
5. What are some practical applications of Farkas' Lemma in optimization problems?

Tip:

In understanding the role of the separating hyperplane theorem in Farkas' Lemma, it’s helpful to think about the geometric implications of the cone generated by $Ax$ and how it relates to the vector $b$.