Lemma 2.2 — [NC_L] iff ‖x‖₀ ≤ s and the coordinate conditions (2.5)
ProvedSparseNLO.Partial.lemma_2_2optimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let be continuously differentiable and bounded below, let , and let . For every , the condition , , holds if and only if and
The lemma replaces the projection condition by explicit coordinate conditions. In this mission it turns the coordinate bounds reached at a limit point of the partial sparse-simplex method into -stationarity.
Formalization Note is the set of nearest points of to . Assumption 1 is kept as the paper's standing hypothesis, though the statement does not need it.
Preamble
import Mathlib import Definitions.Def_SparseNLO_Partial_Setting
Formal statement
namespace SparseNLO.Partial
/-- 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) ↔
(l0 x ≤ s ∧
(∀ i ∈ I0 x, |gradient f x i| ≤ L * Ms s x) ∧
(∀ i ∈ I1 x, gradient f x i = 0)) := by sorry
end SparseNLO.Partial
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.