Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.2 — Farkas' Lemma for Disjunctive Sets

Proved
Disjunctive.IntroDuality.farkas_lemma_disjunctive

by Shuze Chen · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

disjunctive-programmingfarkas-lemmalinear-programming-duality

This 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 QQQ be a finite index set, and for each h∈Qh \in Qh∈Q let AhA_hAh​ be an mh×nm_h \times nmh​×n matrix and bh∈Rmhb_h \in \mathbb{R}^{m_h}bh​∈Rmh​, defining the polyhedron Ph:={x∈Rn:Ahx≥bh}P_h := \{x \in \mathbb{R}^n : A_h x \ge b_h\}Ph​:={x∈Rn:Ah​x≥bh​}. Let F:=⋃h∈QPhF := \bigcup_{h \in Q} P_hF:=⋃h∈Q​Ph​ be the disjunctive set they form, and let Q∗:={h∈Q:Ph≠∅}Q^* := \{h \in Q : P_h \ne \emptyset\}Q∗:={h∈Q:Ph​=∅}. Then, for α∈Rn\alpha \in \mathbb{R}^nα∈Rn and α0∈R\alpha_0 \in \mathbb{R}α0​∈R:

(∀x∈F, αx≥α0)  ⟺  (∀h∈Q∗, ∃ uh≥0 with uhAh=α and α0≤uhbh).\big(\forall x \in F,\ \alpha x \ge \alpha_0\big) \iff \Big(\forall h \in Q^*,\ \exists\, u_h \ge 0 \text{ with } u_h A_h = \alpha \text{ and } \alpha_0 \le u_h b_h\Big).(∀x∈F, αx≥α0​)⟺(∀h∈Q∗, ∃uh​≥0 with uh​Ah​=α and α0​≤uh​bh​).

The forward direction reduces to the classical (single-polyhedron) Farkas' Lemma applied separately to each nonempty PhP_hPh​: 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 ∣Q∣=1|Q|=1∣Q∣=1) to ordinary Farkas' Lemma.

Formalization Note. This theorem is about a genuine union of possibly-differently-shaped polyhedra (mhm_hmh​ may depend on hhh), 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 uAuAuA.

Preamble
import Mathlib
import Definitions.Def_Disjunctive_IntroDuality_PolyhedralSystems
Formal statement
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
Source
Balas, Disjunctive Programming, Springer 2018, DOI 10.1007/978-3-030-00148-3, p. 9, Theorem 1.2
Human review
  • Endorsed by Community (Bot) · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me