wolfe_faithful_major_cycle
For 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 S' are Wolfe corrals contained in atoms, and there exists an atom p_in ∈ atoms with ∑ i : Fin n, w i * (p_in i - w i) < 0 minimizing ∑ i, w i * q i over atoms, and strictly positive weights c on S summing to 1 with w = ∑ p ∈ S, c p • p, such that starting from T_init = insert p_in S with weights lam_init vanishing on p_in and equal to c on S, the reflexive-transitive closure of wolfe_minor_step reaches (S', lam_final) for some lam_final.
Statement
def wolfe_faithful_major_cycle {n : ℕ} (atoms : Set (Fin n → ℝ)) (S S' : Finset (Fin n → ℝ)) (w w' : Fin n → ℝ) : Prop
- Defined in
- arXiv:2611.12680 Sec. 2.2 Algorithm 2
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 2
- is_wolfe_corralA non-empty finite set S of atoms in ℝ^n is a corral with affine minimizer w if w is an affine combination of S with strictly positive…
- wolfe_minor_stepFor states (T, lam) and (T', lam') in Finset (Fin n → ℝ) × ((Fin n → ℝ) → ℝ), wolfe_minor_step asserts that T is not a Wolfe corral, and…
- Used by 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_run_terminal_optimalityFor 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…
Read back from the Lean
The definition wolfe_faithful_major_cycle defines a transition relation for one major cycle of Wolfe's minimum-norm point algorithm in ℝⁿ. Given a set of points atoms : Set (Fin n → ℝ), two finite subsets S, S' : Finset (Fin n → ℝ), and two vectors w, w' : Fin n → ℝ, it asserts that:
1. S is a Wolfe corral with point w (is_wolfe_corral S w).
2. S' is a Wolfe corral with point w' (is_wolfe_corral S' w').
3. Every element of S belongs to atoms.
4. Every element of S' belongs to atoms.
5. There exist an atom p_in : Fin n → ℝ and a coefficient function c : (Fin n → ℝ) → ℝ such that:
a. p_in ∈ atoms.
b. The inner product ⟨w, p_in - w⟩ is strictly negative: ∑ i, w i * (p_in i - w i) < 0 (which implies p_in ∉ S).
c. p_in minimizes the linear functional ⟨w, ·⟩ over atoms: for all q ∈ atoms, ∑ i, w i * p_in i ≤ ∑ i, w i * q i.
d. c is a strictly positive convex combination on S representing w, and is zero outside S:
∑ p ∈ S, c p = 1,
∀ p ∈ S, c p > 0,
∀ p ∉ S, c p = 0,
and w = ∑ p ∈ S, c p • p.
e. Defining lam_init p = if p = p_in then 0 else c p (which is equal to c p since p_in ∉ S) and T_init = insert p_in S,
f. There exists a function lam_final : (Fin n → ℝ) → ℝ such that the state (S', lam_final) is reachable from (T_init, lam_init) in zero or more steps of the minor step relation wolfe_minor_step (via Relation.ReflTransGen).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A major cycle under Wolfe's linopt rule, executing minor cycles from the inserted atom. -/ def wolfe_faithful_major_cycle {n : ℕ} (atoms : Set (Fin n → ℝ)) (S S' : Finset (Fin n → ℝ)) (w w' : Fin n → ℝ) : Prop := is_wolfe_corral S w ∧ is_wolfe_corral S' w' ∧ (∀ p ∈ S, p ∈ atoms) ∧ (∀ p ∈ S', p ∈ atoms) ∧ ∃ (p_in : Fin n → ℝ) (c : (Fin n → ℝ) → ℝ), p_in ∈ atoms ∧ (∑ i : Fin n, w i * (p_in i - w i) < 0) ∧ (∀ q ∈ atoms, ∑ i : Fin n, w i * p_in i ≤ ∑ i : Fin n, w i * q i) ∧ (∑ p ∈ S, c p = 1) ∧ (∀ p ∈ S, 0 < c p) ∧ (∀ p ∉ S, c p = 0) ∧ (w = ∑ p ∈ S, c p • p) ∧ let lam_init : (Fin n → ℝ) → ℝ := fun p => if p = p_in then 0 else c p let T_init : Finset (Fin n → ℝ) := insert p_in S ∃ lam_final : (Fin n → ℝ) → ℝ, Relation.ReflTransGen wolfe_minor_step (T_init, lam_init) (S', lam_final)