§4.2.1, proof of Theorem 3.3, (4.2) — if ‖x*‖₀ < s then f(x*) ≤ min_t f(x* + teᵢ) for every i ∈ I₁(x*)
ProvedSparseNLO.Greedy.eq_4_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). Let be an accumulation point of with , and let . Then
that is, (4.2).
This is the support half of the case in the proof of Theorem 3.3; the same argument also yields Lemma 3.3 for the partial sparse-simplex method.
Formalization Note "Accumulation point" is MapClusterPt xstar atTop x. Indices are and is EuclideanSpace.single i t. The minimum in (4.2) is attained (at , by the inequality itself), so " the minimum" is written as " every value". 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, (4.2) (p. 29): if `x*` is an accumulation point of a run of
the greedy sparse-simplex method with `‖x*‖₀ < s`, then for every `i ∈ I₁(x*)`,
`f(x*) ≤ f(x* + t eᵢ)` for all `t ∈ ℝ`, i.e. `f(x*) ≤ min_t f(x* + t eᵢ)`. -/
theorem eq_4_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)
(xstar : EuclideanSpace ℝ (Fin n)) (hacc : MapClusterPt xstar atTop x)
(hstar : SparseNLO.CWOpt.l0 xstar < s) (i : Fin n) (hi : i ∈ SparseNLO.CWOpt.I1 xstar) :
∀ t : ℝ, f xstar ≤ f (xstar + EuclideanSpace.single i 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, (4.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.