AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

Lean source view module on GitHub

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)
See it in the graphDiscuss this resultChallenge it