wolfe_faithful_run_terminal_optimality
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`.
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`.
∀ q ∈ atoms, 0 ≤ ∑ i : Fin n, w (Fin.last k) i * (q i - w (Fin.last k) i) := hrun.2
- The proof is a direct record projection (`hrun.2`) because the terminal optimality condition is explicitly included as the second conjunct in the definition of `wolfe_faithful_linopt_run`.
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