Math Problem Statement

prove the farkas lemma

Solution

Farkas' Lemma is a fundamental result in linear algebra and optimization. It provides a condition for the solvability of a system of linear inequalities. The lemma states:

Farkas' Lemma: Given a matrix ARm×nA \in \mathbb{R}^{m \times n} and a vector bRmb \in \mathbb{R}^m, exactly one of the following two statements is true:

  1. There exists a vector xRnx \in \mathbb{R}^n such that Ax=bAx = b and x0x \geq 0 (component-wise).
  2. There exists a vector yRmy \in \mathbb{R}^m such that yTA0y^T A \geq 0 and yTb<0y^T b < 0.

Proof of Farkas' Lemma:

  1. Suppose (1) is true:

    • If there exists x0x \geq 0 such that Ax=bAx = b, we need to show that (2) cannot be true.
    • Assume yRmy \in \mathbb{R}^m is such that yTA0y^T A \geq 0 and yTb<0y^T b < 0.
    • Then, yTb=yTAxy^T b = y^T A x, since Ax=bAx = b.
    • However, since yTA0y^T A \geq 0 and x0x \geq 0, yTAx0y^T A x \geq 0, contradicting the assumption that yTb<0y^T b < 0.
    • Therefore, if (1) holds, (2) must be false.
  2. Suppose (1) is false:

    • This means there is no x0x \geq 0 such that Ax=bAx = b.
    • We aim to prove that (2) must then be true, which would mean that there exists yy such that yTA0y^T A \geq 0 and yTb<0y^T b < 0.
    • Consider the set C={Ax:x0}C = \{Ax : x \geq 0\}. This is a convex cone in Rm\mathbb{R}^m.
    • Since bCb \notin C, by the separating hyperplane theorem, there exists a hyperplane defined by a non-zero vector yy that strictly separates bb from CC.
    • Specifically, yy satisfies yTA0y^T A \geq 0 for all x0x \geq 0, meaning yTC0y^T C \geq 0, and yTb<0y^T b < 0.
    • This establishes (2).

Thus, either xx exists satisfying the first condition, or yy exists satisfying the second condition, but not both.

Would you like to explore this proof further or have any questions?

Related Questions

  1. How does Farkas' Lemma relate to the theory of linear programming?
  2. Can you provide an example where Farkas' Lemma is applied?
  3. What is the geometric interpretation of Farkas' Lemma?
  4. How does Farkas' Lemma connect with the Duality Theorem in linear programming?
  5. What are some generalizations of Farkas' Lemma?

Tip:

Understanding the geometric interpretation of Farkas' Lemma can provide deeper insights into linear programming and optimization problems.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Linear Algebra
Optimization

Formulas

-

Theorems

Farkas' Lemma

Suitable Grade Level

Advanced Undergraduate