The following lemma (called Farkas’ Lemma) is a useful consequence of the separating hyperplane theorem. Lemma 1. Let A ∈ RM×N and b ∈ RM. Exactly one of the following is true: (a) there exists a vector x ∈ R N + such that Ax = b. (b) there exists λ ∈ RM such that AT λ ≤ 0, and λ T · b > 0.Prove the lemma (for arbitrary A).

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

Explore the proof of Farkas' Lemma using linear algebra and convex sets. Understand the implications of the lemma in optimization and linear programming. Suitable for advanced undergraduate students and beyond.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation