(2.18), proof of Theorem 2.4 — f(x* − x*ₘeₘ − σx*ₘeᵢ) ≤ f(x*) − σx*ₘ∇ᵢf(x*) + L₂(f)(x*ₘ)² at a CW-minimum with ‖x*‖₀ = s
ProvedSparseNLO.CWOpt.eq_2_18Let be continuously differentiable and bounded below with Lipschitz gradient (Assumption 2), let , and let satisfy the local Lipschitz condition (2.15). Let be a coordinate-wise minimum of (P) with . Let , let be an index with , and set
Then
This is the estimate that, combined with the CW-minimality inequality of (2.17), yields the bound on the zero coordinates in Theorem 2.4.
Formalization Note The statement is the first and the last member of the chain (2.18). The printed middle equality uses , which needs ; when () the norm is and the inequality still holds because . The sign is SignType.sign cast to , with . The facts and used on the page are consequences of the hypotheses, not assumptions.
import Mathlib import Definitions.Def_SparseNLO_CWOpt_Setting
namespace SparseNLO.CWOpt
/-- (2.18), proof of Theorem 2.4 (p. 12): let `x*` be a CW-minimum with `‖x*‖₀ = s`, let
`i ∈ I₀(x*)`, let `m` be an index with `|x*_m| = M_s(x*)`, and `σ = sgn(x*_m ∇_i f(x*))`. Then
`f(x* − x*_m e_m − σ x*_m e_i) ≤ f(x*) − σ x*_m ∇_i f(x*) + L2 (x*_m)²`. -/
theorem eq_2_18 {n s : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ContDiff ℝ 1 f)
(hbdd : ∃ γ : ℝ, ∀ x, γ ≤ f x) (hs : 0 < s) (hsn : s < n)
(Lf : NNReal) (hLf : LipschitzWith Lf (gradient f))
(L2 : ℝ) (hL2 : LocalLipschitz f L2)
(xstar : EuclideanSpace ℝ (Fin n)) (hcw : IsCWMin f s xstar) (hxs : l0 xstar = s)
(i : Fin n) (hi : i ∈ I0 xstar) (m : Fin n) (hm : |xstar m| = Ms s xstar) :
f (xstar - EuclideanSpace.single m (xstar m)
- EuclideanSpace.single i ((SignType.sign (xstar m * gradient f xstar i) : ℝ) * xstar m))
≤ f xstar - (SignType.sign (xstar m * gradient f xstar i) : ℝ) * xstar m * gradient f xstar i
+ L2 * xstar m ^ 2 := by sorry
end SparseNLO.CWOpt
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.