EconCSLib.LinearProgramming.lp_weak_duality
theoremverifiedformalizationimported Lean
EconCSLib.LinearProgramming.lp_weak_duality
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators 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_weak_duality (A : I β Fin n β π) (b : I β π) (c : Fin n β π) {x : Fin n β π} (hxA : β i, b i β€ β j, A i j * x j) (hxnn : β j, 0 β€ x j) {u : I β π} (hu_du : DualFeasible A c u) : β i, u i * b i β€ β j, c j * x j
- Formalizes
- EconCSLib, `EconCSLib.LinearProgramming.lp_weak_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_weak_duality← EconCSLib.LinearProgramming.lp_weak_duality (EconCSLib/Math/LinearProgramming/StrongDuality.lean:61): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- EconCSLib.LinearProgramming.DualFeasibleDual feasibility of
u:u β₯ 0 β§ uα΅A β€ c.
- EconCSLib.LinearProgramming.DualFeasibleDual feasibility of
- Used by 2
- EconCSLib.LinearProgramming.exists_row_strict_pairPer-row strict-CS witness: for each row
iβ, there exists an optimal primal-dual pair with(Ax - b)_{iβ} + u_{iβ} > 0. Hypotheses:β¦ - EconCSLib.LinearProgramming.exists_col_strict_pairPer-column strict-CS witness: for each column
jβ, there exists an optimal primal-dual pair withx_{jβ} + (c - uα΅A)_{jβ} > 0.
- EconCSLib.LinearProgramming.exists_row_strict_pairPer-row strict-CS witness: for each row
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 inset_option linter.unusedSectionVars false invariable {π : Type*} [Field π] [LinearOrder π] [IsStrictOrderedRing π] invariable {I : Type*} [Fintype I] [DecidableEq I] {n : β} intheorem EconCSLib.LinearProgramming.lp_weak_duality (A : I β Fin n β π) (b : I β π) (c : Fin n β π) {x : Fin n β π} (hxA : β i, b i β€ β j, A i j * x j) (hxnn : β j, 0 β€ x j) {u : I β π} (hu_du : DualFeasible A c u) : β i, u i * b i β€ β j, c j * x j := by obtain β¨hu_nn, hu_leβ© := hu_du -- β¨u, bβ© β€ β¨u, A xβ© (componentwise from Ax β₯ b, weighted by u β₯ 0) -- = β¨uα΅A, xβ© -- β€ β¨c, xβ© (componentwise from uα΅A β€ c, weighted by x β₯ 0) calc β i, u i * b i β€ β i, u i * (β j, A i j * x j) := by apply Finset.sum_le_sum intro i _ exact mul_le_mul_of_nonneg_left (hxA i) (hu_nn i) _ = β j, (β i, u i * A i j) * x j := by have h1 : (β i, u i * β j, A i j * x j) = β i, β j, u i * (A i j * x j) := by refine Finset.sum_congr rfl (fun i _ => ?_) rw [Finset.mul_sum] have h2 : (β i, β j, u i * (A i j * x j)) = β j, β i, u i * (A i j * x j) := Finset.sum_comm have h3 : (β j, β i, u i * (A i j * x j)) = β j, (β i, u i * A i j) * x j := by refine Finset.sum_congr rfl (fun j _ => ?_) rw [Finset.sum_mul] refine Finset.sum_congr rfl (fun i _ => ?_) ring rw [h1, h2, h3] _ β€ β j, c j * x j := by apply Finset.sum_le_sum intro j _ exact mul_le_mul_of_nonneg_right (hu_le j) (hxnn j)