Lemma 1.4.1 — homogeneous Farkas lemma: is infeasible iff with
ProvedModernConvex.LPDuality.homogeneous_farkas_lemmaLet and consider the system of homogeneous linear inequalities in
Then
This is the special case of the general theorem on the alternative from which the book derives the general case (Exercise 1.9), and so the root of the LP duality theorem.
Formalization Note ranges over with componentwise; is the dot product. Both directions of the equivalence are stated.
import Mathlib open Matrix
namespace ModernConvex.LPDuality
/-- Ben-Tal–Nemirovski, Lemma 1.4.1 (the homogeneous Farkas lemma), p. 34:
the system `(F) : aᵀx < 0, aᵢᵀx ≥ 0 (i = 1, …, m)` is infeasible iff `a = ∑ λᵢaᵢ` with `λ ≥ 0`. -/
theorem homogeneous_farkas_lemma {m n : ℕ} (a : Fin n → ℝ) (as : Fin m → Fin n → ℝ) :
(¬ ∃ x : Fin n → ℝ, a ⬝ᵥ x < 0 ∧ ∀ i, 0 ≤ as i ⬝ᵥ x) ↔
∃ l : Fin m → ℝ, 0 ≤ l ∧ a = ∑ i, l i • as i := by sorry
end ModernConvex.LPDuality
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix natural numbers , a vector , and vectors . Write for the standard dot product. The statement asserts the equivalence of two conditions.
Condition 1. There is no satisfying both
Condition 2. There exists with for every (the inequality is componentwise) such that
This is a full "if and only if". The inequality on is strict; the inequalities on the are non-strict.
Degenerate cases:
- : the sum is empty and equals , so the right side says . The left side says no has , which also holds exactly when .
- : every vector is the zero vector and every dot product is . Both sides are then true.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.