Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Carathéodory's theorem of cones ([7, p. 689]), as used for (4.3), p. 7 — a linearly independent sub-representation

Proved
AugLagLLC.Feas.caratheodory_cones

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

caratheodoryconvex-coneslinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let VVV be a real vector space, let aia_iai​ (i∈ιi\in\iotai∈ι, a finite index set) and bjb_jbj​ (j∈κj\in\kappaj∈κ) be vectors of VVV, and let J0⊆κJ_0\subseteq\kappaJ0​⊆κ be finite. Suppose

w=∑i∈ιαiai+∑j∈J0βjbjwith βj≥0 (j∈J0).w=\sum_{i\in\iota}\alpha_i a_i+\sum_{j\in J_0}\beta_j b_j\qquad\text{with }\beta_j\ge0\ (j\in J_0).w=i∈ι∑​αi​ai​+j∈J0​∑​βj​bj​with βj​≥0 (j∈J0​).

Then there are subsets I⊆ιI\subseteq\iotaI⊆ι and J⊆J0J\subseteq J_0J⊆J0​ and coefficients α^i\hat\alpha_iα^i​ (i∈Ii\in Ii∈I) and β^j≥0\hat\beta_j\ge0β^​j​≥0 (j∈Jj\in Jj∈J) such that

w=∑i∈Iα^iai+∑j∈Jβ^jbjw=\sum_{i\in I}\hat\alpha_i a_i+\sum_{j\in J}\hat\beta_j b_jw=i∈I∑​α^i​ai​+j∈J∑​β^​j​bj​

and the vectors {ai}i∈I∪{bj}j∈J\{a_i\}_{i\in I}\cup\{b_j\}_{j\in J}{ai​}i∈I​∪{bj​}j∈J​ 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 ai=∇[h2(xk)]ia_i=\nabla[h_2(x_k)]_iai​=∇[h2​(xk​)]i​, bj=∇[g2(xk)]jb_j=\nabla[g_2(x_k)]_jbj​=∇[g2​(xk​)]j​ and J0J_0J0​ the constraints active at x∗x_*x∗​, 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 I⊕JI\oplus JI⊕J, so a vector appearing twice counts as dependent. Mathlib has only the convex-hull form of Carathéodory's theorem.

Preamble
import Mathlib
Formal statement
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
Source
Andreani, Birgin, Martínez & Schuverdt, On augmented Lagrangian methods with general lower-level constraints, HAL hal-01295437v1, p. 7, proof of Theorem 4.1, the step leading to (4.3), citing Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific 1999, p. 689 (Carathéodory's theorem for cones)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me