AFTD Auto-Formalizing Theoretical Domains

EconCSLib.LinearProgramming.lp_weak_complementarity_col

theoremverifiedformalizationimported Lean

Weak complementary slackness, column form.

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_complementarity_col
    (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)
    (h_match : βˆ‘ j, c j * x j = βˆ‘ i, u i * b i) :
    βˆ€ j, (c j - βˆ‘ i, u i * A i j) * x j = 0
Formalizes
EconCSLib, `EconCSLib.LinearProgramming.lp_weak_complementarity_col`
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

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 : β„•} in/-- **Weak complementary slackness**, column form. -/theorem EconCSLib.LinearProgramming.lp_weak_complementarity_col    (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)    (h_match : βˆ‘ j, c j * x j = βˆ‘ i, u i * b i) :    βˆ€ j, (c j - βˆ‘ i, u i * A i j) * x j = 0 := by  obtain ⟨hu_nn, hu_le⟩ := hu_du  -- Sum identity: βˆ‘ u_i * (A x - b)_i + βˆ‘ x_j * (c - uα΅€A)_j = ⟨c, x⟩ - ⟨u, b⟩ = 0.  have hsum1 : (βˆ‘ i, u i * (βˆ‘ j, A i j * x j - b i))             + (βˆ‘ j, x j * (c j - βˆ‘ i, u i * A i j)) = 0 := by    have h1 : (βˆ‘ i, u i * (βˆ‘ j, A i j * x j - b i))            = (βˆ‘ i, βˆ‘ j, u i * (A i j * x j)) - βˆ‘ i, u i * b i := by      rw [← Finset.sum_sub_distrib]      refine Finset.sum_congr rfl (fun i _ => ?_)      rw [mul_sub, Finset.mul_sum]    have h2 : (βˆ‘ j, x j * (c j - βˆ‘ i, u i * A i j))            = (βˆ‘ j, c j * x j) - (βˆ‘ j, x j * βˆ‘ i, u i * A i j) := by      rw [← Finset.sum_sub_distrib]      refine Finset.sum_congr rfl (fun j _ => ?_)      rw [mul_sub, mul_comm (x j) (c j)]    have hcross : (βˆ‘ i, βˆ‘ j, u i * (A i j * x j))                = (βˆ‘ j, x j * βˆ‘ i, u i * A i j) := by      rw [Finset.sum_comm]      refine Finset.sum_congr rfl (fun j _ => ?_)      rw [Finset.mul_sum]      refine Finset.sum_congr rfl (fun i _ => ?_)      ring    rw [h1, h2, hcross]    linarith [h_match]  have hterm_row : βˆ€ i ∈ Finset.univ, 0 ≀ u i * (βˆ‘ j, A i j * x j - b i) := by    intro i _    exact mul_nonneg (hu_nn i) (by linarith [hxA i])  have hterm_col : βˆ€ j ∈ Finset.univ, 0 ≀ x j * (c j - βˆ‘ i, u i * A i j) := by    intro j _    exact mul_nonneg (hxnn j) (by linarith [hu_le j])  have hsum_row_nn : 0 ≀ βˆ‘ i, u i * (βˆ‘ j, A i j * x j - b i) :=    Finset.sum_nonneg hterm_row  have hsum_col_nn : 0 ≀ βˆ‘ j, x j * (c j - βˆ‘ i, u i * A i j) :=    Finset.sum_nonneg hterm_col  have hsum_col_zero : βˆ‘ j, x j * (c j - βˆ‘ i, u i * A i j) = 0 := by linarith  intro j  have hindiv : x j * (c j - βˆ‘ i, u i * A i j) = 0 :=    (Finset.sum_eq_zero_iff_of_nonneg hterm_col).mp hsum_col_zero j (Finset.mem_univ j)  rw [mul_comm] at hindiv  exact hindiv
See it in the graphDiscuss this resultChallenge it