Theorem 3.3 — every accumulation point of the greedy sparse-simplex method is a coordinate-wise minimum of (P)
ProvedSparseNLO.Greedy.theorem_3_3Let be continuously differentiable and bounded below (Assumption 1), and let be an integer. Consider the sparsity constrained problem
Let be a sequence generated by the greedy sparse-simplex method. Then every accumulation point of is a coordinate-wise minimum of (P) (Definition 2.4): , and
- if , then for every and every ;
- if , then for every , every and every .
The theorem needs no Lipschitz assumption on . Combined with Theorem 2.4 (every CW-minimum is an -stationary point), it shows that under Assumption 2 the limit points of the method are -stationary points (Corollary 3.2), without knowledge of any Lipschitz constant.
Formalization Note A run of the method is any sequence satisfying the step rule, with every choice of minimizers allowed, and a STOP modelled as ; the theorem holds for every run. "Accumulation point" is MapClusterPt xstar atTop x. Indices are and is EuclideanSpace.single i t.
import Definitions.Def_SparseNLO_Greedy_Method open Filter Topology
namespace SparseNLO.Greedy
/-- Theorem 3.3 (p. 19): let `{xᵏ}` be a sequence generated by the greedy sparse-simplex method
for (P), where `f` is continuously differentiable and bounded below (Assumption 1) and
`0 < s < n`. Then every accumulation point of `{xᵏ}` is a CW-minimum of (P). -/
theorem theorem_3_3
{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)
(xstar : EuclideanSpace ℝ (Fin n)) (hacc : MapClusterPt xstar atTop x) :
SparseNLO.CWOpt.IsCWMin f s xstar := by sorry
end SparseNLO.Greedy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.