wolfe_minor_step
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