基于Andersen教授方法，如何用Farkas'引理验证线性规划不可行性？

Great question! Let’s break down exactly how to apply Farkas' lemma as a "proof certificate" for infeasibility, following the framework E.D. Andersen outlined. The core idea is that instead of trying to directly show no solution exists, you find a vector that satisfies a complementary set of constraints—this vector acts as your concrete proof.

Step 1: Formalize Your Infeasibility Problem #

First, convert your linear programming (LP) constraints into the standard equality + non-negative form that Farkas' lemma targets:

• If your original constraints are (Ax \leq b, x \geq 0), introduce slack variables (s \geq 0) to turn it into (Ax + s = b, x \geq 0, s \geq 0).
• For mixed equality/inequality constraints, handle inequalities similarly by adding or subtracting slack variables as needed.

Let’s use a concrete example to walk through: suppose we want to prove this system is infeasible:

x₁ + x₂ = 1
-x₁ - x₂ = 1
x₁, x₂ ≥ 0

Step 2: Write the Dual Farkas Constraints #

Farkas' lemma states that the system (Ax = b, x \geq 0) is infeasible if and only if there exists a vector (y) such that:

1. (y^T A \geq 0^T) (the transpose of (y) multiplied by (A) results in a non-negative row vector)
2. (y^T b < 0) (the transpose of (y) multiplied by (b) is a negative scalar)

For our example:

• (A = \begin{bmatrix}1 & 1 \ -1 & -1\end{bmatrix}), (b = \begin{bmatrix}1 \ 1\end{bmatrix})
• The constraints for (y = [y₁, y₂]^T) simplify to:
  • (y₁ - y₂ ≥ 0) (from both columns of (A))
  • (y₁ + y₂ < 0) (from the (b) vector)

Step 3: Find a Valid (y) Vector #

You only need any vector (y) that satisfies the above constraints. For our example, pick (y₁ = -1), (y₂ = -1):

• Check (y^T A = [-1, -1] \begin{bmatrix}1 & 1 \ -1 & -1\end{bmatrix} = [0, 0]), which meets the non-negative requirement (condition 1)
• Check (y^T b = (-1)(1) + (-1)(1) = -2 < 0), which satisfies condition 2

Finding this (y) is sufficient to prove the original system (and its corresponding LP) is infeasible.

Step 4: Practical Tips for Real-World LPs #

In practice, you rarely need to compute (y) manually:

• Most optimization solvers will automatically generate this Farkas vector when they detect infeasibility. You can pull it directly from the solver's output logs or diagnostic reports.
• For larger systems, you can set up a small auxiliary LP to find (y): minimize (t) subject to (y^T A ≥ 0^T), (y^T b ≤ -t), (t ≥ 0). If the minimum (t) is positive, you’ve found your proof vector.

内容的提问来源于stack exchange，提问作者ElementX