Lemma 3.2 — the greedy sparse-simplex method is monotone, f(xᵏ⁺¹) ≤ f(xᵏ), with equality iff xᵏ = xᵏ⁺¹ is a CW-minimum
ProvedSparseNLO.Greedy.lemma_3_2coordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let be continuously differentiable and bounded below (Assumption 1), let be an integer, and let be a sequence generated by the greedy sparse-simplex method for (P). Then for every ,
and equality holds if and only if and is a coordinate-wise minimum of (P) (Definition 2.4).
The lemma records that the method generates a nonincreasing sequence of function values and gets stuck only at CW-minima. It is the first step of the proof of Theorem 3.3.
Formalization Note A STOP of the method is modelled by , so the sequence is defined for every . Assumption 1 is the paper's standing assumption and is kept as a hypothesis, although the statement does not need it.
Preamble
import Definitions.Def_SparseNLO_Greedy_Method open Filter Topology
Formal statement
namespace SparseNLO.Greedy
/-- Lemma 3.2 (p. 19): along every run of the greedy sparse-simplex method,
`f(xᵏ⁺¹) ≤ f(xᵏ)` for every `k ≥ 0`, with equality if and only if `xᵏ = xᵏ⁺¹` and `xᵏ` is a
CW-minimum. -/
theorem lemma_3_2
{n s : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f)
(hbdd : ∃ γ : ℝ, ∀ x, γ ≤ f x) (hs : 0 < s) (hsn : s < n)
(x : ℕ → EuclideanSpace ℝ (Fin n)) (hrun : IsGreedyRun f s x) :
∀ k : ℕ, f (x (k + 1)) ≤ f (x k) ∧
(f (x (k + 1)) = f (x k) ↔ x k = x (k + 1) ∧ SparseNLO.CWOpt.IsCWMin f s (x k)) := by sorry
end SparseNLO.Greedy
Source
Beck, Eldar, Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms, SIAM J. Optim. (2013), doi:10.1137/120869778 (source: arXiv:1203.4580v1), p. 19, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.