EconCSLib.LinearProgramming.lp_strong_duality
theoremverifiedformalizationimported Lean
LP Strong Duality [MFoGT, Section 2.8, Exercise 9]: if the primal LP min ⟨c, x⟩ s.t. A x ≥ b, x ≥ 0 is feasible and bounded below by d, then there exists a dual-feasible u with ⟨u, b⟩ ≥ d.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators EconCSLib.LinearAlgebra in set_option linter.unusedSectionVars false in variable {𝕜 : Type*} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] in variable {I : Type*} [Fintype I] [DecidableEq I] {n : ℕ} in theorem EconCSLib.LinearProgramming.lp_strong_duality (A : I → Fin n → 𝕜) (b : I → 𝕜) (c : Fin n → 𝕜) (d : 𝕜) (hP_feas : PrimalFeasible A b) (hP_bound : ∀ x : Fin n → 𝕜, (∀ i, b i ≤ ∑ j, A i j * x j) → (∀ j, 0 ≤ x j) → d ≤ ∑ j, c j * x j) : ∃ u : I → 𝕜, DualFeasible A c u ∧ d ≤ ∑ i, u i * b i
- Formalizes
- EconCSLib, `EconCSLib.LinearProgramming.lp_strong_duality`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.EconCSLib.LinearProgramming.lp_strong_duality← EconCSLib.LinearProgramming.lp_strong_duality (EconCSLib/Math/LinearProgramming/StrongDuality.lean:154): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- EconCSLib.LinearProgramming.dualAugBAugmented RHS.
- EconCSLib.LinearProgramming.DualAugRowAugmented row index for the LP-Farkas reduction.
- EconCSLib.LinearProgramming.dualAugA_inlEconCSLib.LinearProgramming.dualAugA_inl
- EconCSLib.LinearProgramming.isFeasible_dualAug_iffAugmented feasibility is the primal feasibility (with
x ≥ 0). - EconCSLib.LinearProgramming.dualAugB_inrEconCSLib.LinearProgramming.dualAugB_inr
- EconCSLib.LinearAlgebra.IsFeasiblePrimal feasibility of the system
A x ≥ b. - EconCSLib.LinearAlgebra.farkas_lemmaFarkas' Lemma (objective-bound form). For a finite linear system
A x ≥ bwithS = {x | A x ≥ b}nonempty, the primal bound "… - EconCSLib.LinearProgramming.dualAugB_inlEconCSLib.LinearProgramming.dualAugB_inl
- EconCSLib.LinearProgramming.dualAugA_inrEconCSLib.LinearProgramming.dualAugA_inr
- EconCSLib.LinearAlgebra.rowEval_defEconCSLib.LinearAlgebra.rowEval_def
- EconCSLib.LinearProgramming.dualAugAAugmented matrix combining
Arows withx ≥ 0unit rows. - EconCSLib.LinearProgramming.DualFeasibleDual feasibility of
u:u ≥ 0 ∧ uᵀA ≤ c. - EconCSLib.LinearProgramming.PrimalFeasiblePrimal feasibility:
∃ x, A x ≥ b ∧ x ≥ 0.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators EconCSLib.LinearAlgebra inset_option linter.unusedSectionVars false invariable {𝕜 : Type*} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] invariable {I : Type*} [Fintype I] [DecidableEq I] {n : ℕ} in/-- **LP Strong Duality** [MFoGT, Section 2.8, Exercise 9]: if the primal LP `min ⟨c, x⟩ s.t. A x ≥ b, x ≥ 0` is feasible and bounded below by `d`, then there exists a dual-feasible `u` with `⟨u, b⟩ ≥ d`. -/theorem EconCSLib.LinearProgramming.lp_strong_duality (A : I → Fin n → 𝕜) (b : I → 𝕜) (c : Fin n → 𝕜) (d : 𝕜) (hP_feas : PrimalFeasible A b) (hP_bound : ∀ x : Fin n → 𝕜, (∀ i, b i ≤ ∑ j, A i j * x j) → (∀ j, 0 ≤ x j) → d ≤ ∑ j, c j * x j) : ∃ u : I → 𝕜, DualFeasible A c u ∧ d ≤ ∑ i, u i * b i := by -- Translate hypotheses to the augmented system. have hAug_feas : IsFeasible (dualAugA A) (dualAugB b) := (isFeasible_dualAug_iff A b).mpr hP_feas have hAug_bound : ∀ x : Fin n → 𝕜, (∀ idx, dualAugB b idx ≤ ∑ j, dualAugA A idx j * x j) → d ≤ ∑ j, c j * x j := by intro x hx apply hP_bound x · intro i have h := hx (Sum.inl i) simpa using h · intro j' have h := hx (Sum.inr j') simp only [dualAugB_inr, dualAugA_inr, ite_mul, one_mul, zero_mul, Fintype.sum_ite_eq'] at h exact h -- Apply Farkas to the augmented system. have hCert := (farkas_lemma (dualAugA A) (dualAugB b) c d hAug_feas).mp hAug_bound obtain ⟨u_aug, hu_nn, hu_col, hu_b⟩ := hCert -- Decompose u_aug into u (on I) and v (on Fin n). refine ⟨fun i => u_aug (Sum.inl i), ?_, ?_⟩ · -- DualFeasible: u ≥ 0 and uᵀA ≤ c. refine ⟨fun i => hu_nn (Sum.inl i), ?_⟩ intro j -- Use the column-j condition on the augmented system. have h := hu_col j -- h : (∑ row, u_aug row * dualAugA A row j) = c j rw [Fintype.sum_sum_type] at h -- h : (∑ i, u_aug (Sum.inl i) * dualAugA A (Sum.inl i) j) + -- (∑ j', u_aug (Sum.inr j') * dualAugA A (Sum.inr j') j) = c j simp only [dualAugA_inl, dualAugA_inr, mul_ite, ite_mul, mul_one, one_mul, mul_zero, zero_mul, Fintype.sum_ite_eq, Fintype.sum_ite_eq'] at h -- h : (∑ i, u_aug (inl i) * A i j) + u_aug (Sum.inr j) = c j -- Goal: ∑ i, u_aug (Sum.inl i) * A i j ≤ c j have hv_nn : 0 ≤ u_aug (Sum.inr j) := hu_nn (Sum.inr j) linarith · -- ⟨u, b⟩ ≥ d have h : (∑ row, u_aug row * dualAugB b row) = ∑ i, u_aug (Sum.inl i) * b i := by rw [Fintype.sum_sum_type] simp only [dualAugB_inl, dualAugB_inr, mul_zero, Finset.sum_const_zero, add_zero] linarith [hu_b, h.symm ▸ hu_b]