Equivalent characterizations of linearly independent active constraints
ProvedLinearOptimization.lp_active_constraint_equivgeometrylinear-programmingpolyhedra
(Theorem 2.2) Let be an element of and let be the set of indices of constraints that are active at . Then, the following are equivalent:
- (a) There exist vectors in the set , which are linearly independent.
- (b) The span of the vectors , , is all of , that is, every element of can be expressed as a linear combination of the vectors , .
- (c) The system of equations , , has a unique solution.
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Mathlib.Data.List.TFAE import Definitions.Def_ActiveConstraints open Matrix /-- **B&T Theorem 2.2 (p. 48).** Equivalent characterizations of "there are `n` linearly independent constraints active at `x*`". In (c), `x*` itself solves the active system, so uniqueness is stated as "every solution equals `x*`". -/
Formal statement
theorem LinearOptimization.lp_active_constraint_equiv {ι : Type} [Fintype ι] {n : ℕ}
(C : ι → LinearConstraint n) (x' : Fin n → ℝ) :
List.TFAE
[ ∃ s : Finset ι, s.card = n ∧ (∀ i ∈ s, (C i).IsActiveAt x') ∧
LinearIndependent ℝ (fun i : s => (C i.1).a),
Submodule.span ℝ ((fun i => (C i).a) '' {i | (C i).IsActiveAt x'}) = ⊤,
∀ y : Fin n → ℝ,
(∀ i, (C i).IsActiveAt x' → (C i).a ⬝ᵥ y = (C i).b) → y = x' ] := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 2.2, p. 48