AFTD Auto-Formalizing Theoretical Domains

wolfe_faithful_run_terminal_optimality

theoremverified

For any faithful Wolfe linopt run hrun of length k on atoms in ℝ^n with corrals S and centers w, the final center w(Fin.last k) satisfies 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i) for all atoms q ∈ atoms.

Statement

theorem wolfe_faithful_run_terminal_optimality {n : ℕ} {atoms : Set (Fin n → ℝ)} {k : ℕ}
    {S : Fin (k + 1) → Finset (Fin n → ℝ)} {w : Fin (k + 1) → (Fin n → ℝ)}
    (hrun : wolfe_faithful_linopt_run atoms k S w) :
    ∀ q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i)
Source
arXiv:2611.12680 Sec. 2.2
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • wolfe_faithful_linopt_runFor atoms : Set (Fin n → ℝ), run length k : ℕ, corrals S : Fin (k + 1) → Finset (Fin n → ℝ), and centers w : Fin (k + 1) → (Fin n → ℝ),…
  • wolfe_faithful_major_cycleFor a set atoms of vectors in ℝ^n, corrals S and S' with centers w and w', wolfe_faithful_major_cycle atoms S S' w w' asserts that S and…

Read back from the Lean

Given a dimension n : ℕ, a set of atoms atoms : Set (Fin n → ℝ), a step count k : ℕ, a sequence of subsets of atoms S : Fin (k + 1) → Finset (Fin n → ℝ), and a sequence of iterates w : Fin (k + 1) → (Fin n → ℝ): Assuming hrun : wolfe_faithful_linopt_run atoms k S w (that is: 1. for every i : Fin k, a faithful Wolfe major cycle transitions from (S i.castSucc, w i.castSucc) to (S i.succ, w i.succ), and 2. for all q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i)), the theorem asserts that for all q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i) (i.e., the terminal iterate w (Fin.last k) satisfies the first-order optimality condition over atoms).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The terminal optimality of a faithful Wolfe linopt run holds directly by definition. In Lean, `wolfe_faithful_linopt_run` is defined as a conjunction where the second conjunct is precisely the statement that the gap is non-negative for all atoms at the final iterate. The proof simply extracts this second component from the assumption `hrun`.

  1. For every atom q in the atom set, the inner product with the final iterate satisfies 0 ≤ ∑ i : Fin n, w(Fin.last k) i * (q i - w(Fin.last k) i).

    By definition, a faithful Wolfe linopt run `wolfe_faithful_linopt_run atoms k S w` is a conjunction of two conditions: (1) valid major cycle transitions between successive corrals and centers, and (2) the terminal optimality condition at the final iterate `w (Fin.last k)`. The proof term `hrun.2` simply projects out the second conjunct of the hypothesis `hrun`.

    line 5

        ∀ q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i) := hrun.2

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Terminal optimality of a faithful Wolfe linopt run: all gaps are non-negative at the end. -/theorem wolfe_faithful_run_terminal_optimality {n : ℕ} {atoms : Set (Fin n → ℝ)} {k : ℕ}    {S : Fin (k + 1) → Finset (Fin n → ℝ)} {w : Fin (k + 1) → (Fin n → ℝ)}    (hrun : wolfe_faithful_linopt_run atoms k S w) :    ∀ q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i) := hrun.2
See it in the graphDiscuss this resultChallenge it