§4.2.1, proof of Theorem 3.3, case ‖x*‖₀ = s — f(x*) ≤ f(x* − x*ᵢeᵢ + teⱼ) for all i ∈ I₁(x*), j, t
ProvedSparseNLO.Greedy.case_support_eq_scoordinate-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). Let be an accumulation point of with . Then
that is, for all and all .
This is the case of the proof of Theorem 3.3: together with feasibility of it is Case II of the definition of a CW-minimum.
Formalization Note "Accumulation point" is MapClusterPt xstar atTop x: every neighbourhood of contains for infinitely many , which in is the existence of a subsequence converging to . Indices are and is EuclideanSpace.single i t. Assumption 1 is the paper's standing assumption.
Preamble
import Definitions.Def_SparseNLO_Greedy_Method open Filter Topology
Formal statement
namespace SparseNLO.Greedy
/-- §4.2.1, proof of Theorem 3.3, case `‖x*‖₀ = s` (p. 29): if `x*` is an accumulation point
of a run of the greedy sparse-simplex method and `‖x*‖₀ = s`, then
`f(x*) ≤ f(x* − x*ᵢ eᵢ + t eⱼ)` for all `i ∈ I₁(x*)`, all `j` and all `t ∈ ℝ`. -/
theorem case_support_eq_s
{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)
(hstar : SparseNLO.CWOpt.l0 xstar = s) :
∀ i ∈ SparseNLO.CWOpt.I1 xstar, ∀ (j : Fin n) (t : ℝ),
f xstar ≤ f (xstar - EuclideanSpace.single i (xstar i) + EuclideanSpace.single j t) := 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. 29, §4.2.1, proof of Theorem 3.3, case ‖x*‖₀ = s
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.