Lemma 2.2 — [NC_L] holds iff ‖x‖₀ ≤ s, ∇ᵢf(x) = 0 on the support and |∇ᵢf(x)| ≤ L·M_s(x) off it (2.5)
ProvedSparseNLO.IHT.lemma_2_2optimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let be continuously differentiable and bounded below (Assumption 1), and let . For any , a vector satisfies
if and only if and
Lemma 2.2 turns the projection condition into explicit coordinate-wise inequalities. It shows that -stationarity becomes weaker as grows, and it is the form in which the limit argument of Theorem 3.1 verifies -stationarity.
Formalization Note is the bare membership in the projection set (the set of all nearest points). Assumption 1 is the paper's standing assumption and is kept although the equivalence does not use it. Indices run over Fin n.
Preamble
import Mathlib import Definitions.Def_SparseNLO_IHT_Setting open Filter Topology
Formal statement
namespace SparseNLO.IHT
/-- Lemma 2.2 (p. 7). For any `L > 0`, `x` satisfies `[NC_L]`, i.e.
`x ∈ P_{C_s}(x − (1/L) ∇f(x))`, if and only if `‖x‖₀ ≤ s` and (2.5):
`|∇_i f(x)| ≤ L · M_s(x)` for `i ∈ I₀(x)` and `∇_i f(x) = 0` for `i ∈ I₁(x)`. -/
theorem lemma_2_2 {n s : ℕ} (hs : 0 < s) (hsn : s < n)
(f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f) (hbdd : ∃ γ : ℝ, ∀ x, γ ≤ f x)
(L : ℝ) (hL : 0 < L) (x : EuclideanSpace ℝ (Fin n)) :
x ∈ projCs n s (x - (1 / L) • gradient f x) ↔
(SparseNLO.CWOpt.l0 x ≤ s ∧
(∀ i ∈ SparseNLO.CWOpt.I0 x, |gradient f x i| ≤ L * SparseNLO.CWOpt.Ms s x) ∧
(∀ i ∈ SparseNLO.CWOpt.I1 x, gradient f x i = 0)) := by sorry
end SparseNLO.IHT
Source
Beck, Eldar, Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms, SIAM J. Optim. (2013), doi:10.1137/120869778 (source: arXiv:1203.4580v1), p. 7, Lemma 2.2, (2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.