Lemma 4.1 — the partial sparse-simplex step decreases f by (4.6) when ‖xᵏ‖₀ < s and by A(xᵏ) (4.7)–(4.8) when ‖xᵏ‖₀ = s
ProvedSparseNLO.Partial.lemma_4_1Let be continuously differentiable and bounded below, with Lipschitz gradient (Assumption 2), let , and let satisfy the local Lipschitz condition (2.15). Let be a sequence generated by the partial sparse-simplex method. Then:
- for every with ,
- for every with ,
where
The lemma converts each step of the method into a quantitative decrease of the objective. Since is bounded below, the decreases are summable, which forces the right-hand sides to vanish along convergent subsequences; this is how Theorem 3.4 is obtained.
Formalization Note The page's lemma speaks of "the sparse-simplex method"; in §4.2.3 this is the partial sparse-simplex method. A STOP of the method is modelled as , so (4.6) then says . The maxima are suprema in , which agree with the maxima on the nonempty index sets involved. Assumptions 1 and 2 are kept as standing hypotheses.
import Mathlib import Definitions.Def_SparseNLO_Partial_Method
namespace SparseNLO.Partial
/-- Lemma 4.1 (p. 30): under Assumption 2, with `L2 > 0` satisfying (2.15), the sequence
generated by the partial sparse-simplex method satisfies, for every `k` with `‖xᵏ‖₀ < s`,
`f(xᵏ) − f(xᵏ⁺¹) ≥ (1/(2 L2)) max_{i=1,…,n} (∇ᵢf(xᵏ))²` (4.6), and for every `k` with
`‖xᵏ‖₀ = s`, `f(xᵏ) − f(xᵏ⁺¹) ≥ A(xᵏ)` (4.7), with `A` as in (4.8). -/
theorem lemma_4_1 {n s : ℕ} (hs : 0 < s) (hsn : s < n)
(f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f) (hbdd : ∃ γ : ℝ, ∀ x, γ ≤ f x)
(Lf : NNReal) (hLf : LipschitzWith Lf (gradient f))
(L2 : ℝ) (hL2pos : 0 < L2) (hL2 : LocalLipschitz f L2)
(x : ℕ → EuclideanSpace ℝ (Fin n)) (hrun : IsPartialRun f s x) :
(∀ k : ℕ, l0 (x k) < s →
1 / (2 * L2) * maxSq Finset.univ (gradient f (x k)) ≤ f (x k) - f (x (k + 1))) ∧
(∀ k : ℕ, l0 (x k) = s → Aval f s L2 (x k) ≤ f (x k) - f (x (k + 1))) := by sorry
end SparseNLO.Partial
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.