AFTD Auto-Formalizing Theoretical Domains

wolfe_faithful_major_cycle

def

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)
See it in the graphDiscuss this resultChallenge it