(4.11)–(4.13), proof of Lemma 4.1 — f(xᵏ) − f(xᵏ⁺¹) ≥ M_s(xᵏ)[max_{I₀}|∇ᵢf(xᵏ)| − L₂M_s(xᵏ)] + xᵏ_{m_k}∇_{m_k}f(xᵏ)
ProvedSparseNLO.Partial.eq_4_13Let 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, let satisfy , and let be the selections with which the step from to is made; in particular minimizes over the support . Then
This is the second half of the decrease estimate (4.7) for saturated iterates: it controls the partial derivatives off the support of , which the swap move of the method targets.
Formalization Note The selections are explicit arguments, because the right-hand side depends on the chosen when several support coordinates tie for the smallest absolute value. The maximum over is a supremum in ; is nonempty because . Assumptions 1 and 2 are kept as standing hypotheses.
import Mathlib import Definitions.Def_SparseNLO_Partial_Method
namespace SparseNLO.Partial
/-- (4.11)–(4.13), proof of Lemma 4.1 (p. 31): under Assumption 2, with `L2 > 0` satisfying
(2.15), if `‖xᵏ‖₀ = s` and the step from `xᵏ` to `xᵏ⁺¹` is made with the selections
`i¹_k, T¹_k, i²_k, m_k, T²_k`, then
`f(xᵏ) − f(xᵏ⁺¹) ≥ M_s(xᵏ) [max_{i∈I₀(xᵏ)} |∇ᵢf(xᵏ)| − L2 M_s(xᵏ)] + xᵏ_{m_k} ∇_{m_k} f(xᵏ)`. -/
theorem eq_4_13 {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 : ℕ) (hk : l0 (x k) = s)
(i1 : Fin n) (T1 : ℝ) (i2 m : Fin n) (T2 : ℝ)
(hstep : StepAt f (x k) (x (k + 1)) i1 T1 i2 m T2) :
Ms s (x k) * (maxAbs (I0 (x k)) (gradient f (x k)) - L2 * Ms s (x k))
+ x k m * gradient f (x k) m ≤ 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.