§4.2.1, proof of Theorem 3.3, (4.5) — if ‖x*‖₀ < s then f(x*) ≤ f(x* + teᵢ) for every i ∈ I₀(x*) and t
ProvedSparseNLO.Greedy.eq_4_5Let 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 , i.e. . Then
This is the off-support half of the case in the proof of Theorem 3.3. Together with (4.2) it gives Case I of the definition of a CW-minimum. The difficulty is that iterates near may sit at the sparsity level , where the method cannot simply add the coordinate and must instead swap out a support coordinate whose value tends to zero.
Formalization Note "Accumulation point" is MapClusterPt xstar atTop x. Indices are and is EuclideanSpace.single i t. Assumption 1 is the paper's standing assumption.
import Definitions.Def_SparseNLO_Greedy_Method open Filter Topology
namespace SparseNLO.Greedy
/-- §4.2.1, proof of Theorem 3.3, (4.5) and the display after it (p. 30): 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 ∈ ℝ`. -/
theorem eq_4_5
{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.I0 xstar) :
∀ t : ℝ, f xstar ≤ f (xstar + EuclideanSpace.single i t) := by sorry
end SparseNLO.Greedy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.