EconCSLib.LinearProgramming.lp_weak_complementarity_row
theoremverifiedformalizationimported Lean
Weak complementary slackness, row 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_row (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) : β i, (β j, A i j * x j - b i) * u i = 0
- Formalizes
- EconCSLib, `EconCSLib.LinearProgramming.lp_weak_complementarity_row`
- 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_complementarity_row← EconCSLib.LinearProgramming.lp_weak_complementarity_row (EconCSLib/Math/LinearProgramming/StrongComplementarity.lean:70): 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
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 : β} in/-- **Weak complementary slackness**, row form. -/theorem EconCSLib.LinearProgramming.lp_weak_complementarity_row (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) : β i, (β j, A i j * x j - b i) * u i = 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] -- Each term in hsum1 is β₯ 0 (nonneg variable times nonneg slack), so each is 0. 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_row_zero : β i, u i * (β j, A i j * x j - b i) = 0 := by linarith -- Each individual term is 0. intro i have hindiv : u i * (β j, A i j * x j - b i) = 0 := (Finset.sum_eq_zero_iff_of_nonneg hterm_row).mp hsum_row_zero i (Finset.mem_univ i) rw [mul_comm] at hindiv exact hindiv