AFTD Auto-Formalizing Theoretical Domains

wolfe_minor_step

def

For states (T, lam) and (T', lam') in Finset (Fin n → ℝ) × ((Fin n → ℝ) → ℝ), wolfe_minor_step asserts that T is not a Wolfe corral, and there exist an affine minimizer μ of T with center w, a step size θ with 0 ≤ θ ≤ 1, and an atom p_drop ∈ T such that (1 - θ) * lam p + θ * μ p ≥ 0 for all p ∈ T, μ(p_drop) < lam(p_drop) with (1 - θ) * lam(p_drop) + θ * μ(p_drop) = 0, lam' = (fun p => (1 - θ) * lam p + θ * μ p), and T' = T.erase p_drop.

Statement

def wolfe_minor_step {n : ℕ}
    (state state' : Finset (Fin n → ℝ) × ((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…
  • is_affine_minimizerFor a finite set T of vectors in ℝ^n, a vector w : Fin n → ℝ, and ambient weights μ : (Fin n → ℝ) → ℝ, is_affine_minimizer T w μ asserts…
Used by 2
  • 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…
  • wolfe_minor_reaches_eq_of_corralIf a support T : Finset (Fin n → ℝ) is a Wolfe corral with center w, then for any ambient weights lam : (Fin n → ℝ) → ℝ, any state final…

Read back from the Lean

For a fixed dimension n : ℕ, wolfe_minor_step state state' is a relation between two states state = (T, lam) and state' = (T', lam'), each consisting of a finite set of points T, T' : Finset (Fin n → ℝ) and a weight function lam, lam' : (Fin n → ℝ) → ℝ. The definition asserts that state' is reachable from state by a single minor step of Wolfe's minimum-norm point algorithm: 1. T is not a Wolfe corral for any point w : Fin n → ℝ (i.e., ¬ ∃ w, is_wolfe_corral T w). 2. There exist a point w : Fin n → ℝ, an affine weight function μ : (Fin n → ℝ) → ℝ, a step size θ : ℝ, and a point p_drop : Fin n → ℝ such that: - (w, μ) is an affine minimizer for T (is_affine_minimizer T w μ); - 0 ≤ θ and θ ≤ 1; - for every p ∈ T, the convex combination of weights is non-negative: 0 ≤ (1 - θ) * lam p + θ * μ p; - p_drop ∈ T; - the weight of p_drop decreases under μ: μ p_drop < lam p_drop; - the updated weight of p_drop becomes exactly zero: (1 - θ) * lam p_drop + θ * μ p_drop = 0; - the new weight function lam' equals the function p ↦ (1 - θ) * lam p + θ * μ p; - the new set T' is T with p_drop removed (T.erase p_drop).

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 single minor cycle step of Wolfe's method moving convex combination weights to the boundary. -/
def wolfe_minor_step {n : ℕ}
    (state state' : Finset (Fin n → ℝ) × ((Fin n → ℝ) → ℝ)) : Prop :=
  let (T, lam) := state
  let (T', lam') := state'
  (¬ ∃ w, is_wolfe_corral T w) ∧
  ∃ (w : Fin n → ℝ) (μ : (Fin n → ℝ) → ℝ) (θ : ℝ) (p_drop : Fin n → ℝ),
    is_affine_minimizer T w μ ∧
    0 ≤ θ ∧ θ ≤ 1 ∧
    (∀ p ∈ T, 0 ≤ (1 - θ) * lam p + θ * μ p) ∧
    p_drop ∈ T ∧ μ p_drop < lam p_drop ∧
    (1 - θ) * lam p_drop + θ * μ p_drop = 0 ∧
    lam' = (fun p => (1 - θ) * lam p + θ * μ p) ∧
    T' = T.erase p_drop
See it in the graphDiscuss this resultChallenge it