Lemma 2 (p. 4) — Z is empty iff some u ≥ 0 has Mᵀu ≤ 0 and uᵀq > 0
ProvedLemkeLCP.Existence.lemma_2_p4Let be a real square matrix of order , , and . Then is empty if and only if there is a vector satisfying
This is a theorem of the alternative of Farkas type. In the proof of Theorem 4 only the direction "a satisfying (5) makes empty" is used: it is how the case of the augmented path is shown to certify infeasibility. The page states it as an equivalence, and so does this item.
Formalization Note It is the specialization of part (ii) of the published Farkas lemma MatousekLP.Duality.farkas_three_variants to , , over a general finite index type. The paper labels two different results "Lemma 2" (pp. 4 and 6); this is the one on p. 4, which the proof of Theorem 4 on p. 8 calls "Lemma 1".
import Mathlib import Definitions.Def_LemkeLCP_Existence_Setting open Matrix
namespace LemkeLCP.Existence
theorem lemma_2_p4 {ι : Type*} [Fintype ι] [DecidableEq ι] (M : Matrix ι ι ℝ) (q : ι → ℝ) :
Z M q = ∅ ↔ ∃ u : ι → ℝ, 0 ≤ u ∧ Mᵀ *ᵥ u ≤ 0 ∧ 0 < u ⬝ᵥ q := by sorry
end LemkeLCP.Existence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.