(4.10), proof of Lemma 4.1 — a saturated step of the partial sparse-simplex method decreases f by at least (1/(2L₂)) max_{i∈I₁(xᵏ)} (∇ᵢf(xᵏ))²
ProvedSparseNLO.Partial.eq_4_10coordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let 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 (with the argmin selection of ).
For every with ,
This is the first half of the decrease estimate (4.7) for saturated iterates: it controls the partial derivatives on the support of .
Formalization Note The maximum over is a supremum in of ; is nonempty because . Assumptions 1 and 2 are kept as standing hypotheses.
Preamble
import Mathlib import Definitions.Def_SparseNLO_Partial_Method
Formal statement
namespace SparseNLO.Partial
/-- (4.10), proof of Lemma 4.1 (p. 31): under Assumption 2, with `L2 > 0` satisfying (2.15),
every step of the partial sparse-simplex method from an iterate with `‖xᵏ‖₀ = s` satisfies
`f(xᵏ) − f(xᵏ⁺¹) ≥ (1/(2 L2)) max_{i∈I₁(xᵏ)} (∇ᵢf(xᵏ))²`. -/
theorem eq_4_10 {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) :
1 / (2 * L2) * maxSq (I1 (x k)) (gradient f (x k)) ≤ f (x k) - f (x (k + 1)) := by sorry
end SparseNLO.Partial
Source
Beck, Eldar, Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms, SIAM J. Optim. (2013), doi:10.1137/120869778 (source: arXiv:1203.4580v1), p. 31, §4.2.3, proof of Lemma 4.1, (4.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.