Carathéodory's theorem of cones ([7, p. 689]), as used for (4.3), p. 7 — a linearly independent sub-representation
ProvedAugLagLLC.Feas.caratheodory_conesLet be a real vector space, let (, a finite index set) and () be vectors of , and let be finite. Suppose
Then there are subsets and and coefficients () and () such that
and the vectors are linearly independent.
This is Carathéodory's theorem for cones with additional free (sign-unconstrained) generators. In the proof of Theorem 4.1 it is applied with , and the constraints active at , producing (4.3); the proof of Theorem 4.2 uses it the same way.
Formalization Note The statement is the generic form of the paper's application; the paper cites it from Bertsekas, Nonlinear Programming, 2nd ed., p. 689. Linear independence is that of the family indexed by the disjoint union , so a vector appearing twice counts as dependent. Mathlib has only the convex-hull form of Carathéodory's theorem.
import Mathlib
namespace AugLagLLC.Feas
theorem caratheodory_cones {V : Type*} [AddCommGroup V] [Module ℝ V]
{ι κ : Type*} [Fintype ι] (a : ι → V) (b : κ → V) (J₀ : Finset κ)
(α : ι → ℝ) (β : κ → ℝ) (hβ : ∀ j ∈ J₀, 0 ≤ β j) :
∃ (I : Finset ι) (J : Finset κ), J ⊆ J₀ ∧
∃ (α' : ι → ℝ) (β' : κ → ℝ), (∀ j ∈ J, 0 ≤ β' j) ∧
∑ i, α i • a i + ∑ j ∈ J₀, β j • b j = ∑ i ∈ I, α' i • a i + ∑ j ∈ J, β' j • b j ∧
LinearIndependent ℝ (Sum.elim (fun i : I => a i) (fun j : J => b j)) := by sorry
end AugLagLLC.Feas
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.