Theorem 1.2 — Farkas' Lemma for Disjunctive Sets
ProvedDisjunctive.IntroDuality.farkas_lemma_disjunctiveThis is Theorem 1.2 of Balas's Disjunctive Programming, the disjunctive generalization of Farkas' Lemma: a characterization of every valid inequality for a disjunctive set, i.e. a union of finitely many polyhedra.
Let be a finite index set, and for each let be an matrix and , defining the polyhedron . Let be the disjunctive set they form, and let . Then, for and :
The forward direction reduces to the classical (single-polyhedron) Farkas' Lemma applied separately to each nonempty : an inequality is valid for a union exactly when it is valid for every piece of the union, and validity for a single polyhedron is certified by ordinary Farkas multipliers. The theorem is the starting point for describing the whole family of valid inequalities — hence cutting planes — for a disjunctive program, and specializes (for ) to ordinary Farkas' Lemma.
Formalization Note. This theorem is about a genuine union of possibly-differently-shaped
polyhedra ( may depend on ), which is a different and strictly more general statement
than the single-polyhedron Farkas' Lemma already on the platform (SmaleNinth.farkas_lemma);
it is not restated as a reference to that theorem. dotProduct is Mathlib's ⬝ᵥ and
Matrix.vecMul u A is the row-vector product .
import Mathlib import Definitions.Def_Disjunctive_IntroDuality_PolyhedralSystems
namespace Disjunctive.IntroDuality
/-- Theorem 1.2 (Balas §1.4, p. 9, [6, 8], Farkas' Lemma for Disjunctive Sets): the inequality
`α x ≥ α₀` is satisfied by every point of the disjunctive set `F = ⋃_{h ∈ Q} P_h` if and only if
for every `h` with `P_h` nonempty there is a multiplier `u_h ≥ 0` with `α = u_h A_h` and
`α₀ ≤ u_h b_h`. -/
theorem farkas_lemma_disjunctive {n : ℕ} {Q : Type*} [Fintype Q] (m : Q → ℕ)
(A : (h : Q) → Matrix (Fin (m h)) (Fin n) ℝ) (b : (h : Q) → Fin (m h) → ℝ)
(α : Fin n → ℝ) (α0 : ℝ) :
(∀ x ∈ ⋃ h : Q, Poly (A h) (b h), α0 ≤ dotProduct α x) ↔
∀ h : Q, (Poly (A h) (b h)).Nonempty →
∃ u : Fin (m h) → ℝ, 0 ≤ u ∧ Matrix.vecMul u (A h) = α ∧
α0 ≤ dotProduct u (b h) := by sorry
end Disjunctive.IntroDuality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.