Farkas' inequality theorem for an arbitrary finite constraint index
ProvedLinearOptimization.farkas_inequality_form_fintypedualityfarkaslinear-programming
Let be an arbitrary finite index set of linear inequalities. Given row vectors , scalars , a cost vector , and , assume that the system for all is feasible. Then the following are equivalent:
and
This is the finite-index-set form of the theorem of alternatives for inequality systems. It allows downstream formalizations to use naturally structured finite constraint types without first encoding them arithmetically as Fin m.
Formalization Note This has exactly the mathematical content of LinearOptimization.farkas_inequality_form; only the finite row index type is generalized.
Preamble
import Mathlib.Data.Matrix.Mul import Mathlib.Data.Real.Basic open Matrix
Formal statement
theorem LinearOptimization.farkas_inequality_form_fintype
{ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(A : Matrix ι (Fin n) ℝ) (b : ι → ℝ) (c : Fin n → ℝ) (d : ℝ)
(hfeas : ∃ x : Fin n → ℝ, A.mulVec x ≤ b) :
(∀ x : Fin n → ℝ, A.mulVec x ≤ b → c ⬝ᵥ x ≤ d) ↔
∃ p : ι → ℝ, 0 ≤ p ∧ Aᵀ.mulVec p = c ∧ p ⬝ᵥ b ≤ d := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.7, p. 166; purely formal finite-index reindexing of the proved Fin m statement