Theorem 2.4 — every CW-minimum x* of (P) satisfies |∇ᵢf(x*)| ≤ L₂(f)M_s(x*) on I₀(x*) and ∇ᵢf(x*) = 0 on I₁(x*)
ProvedSparseNLO.CWOpt.theorem_2_4Let be continuously differentiable and bounded below (Assumption 1), with -Lipschitz gradient (Assumption 2), and let be an integer. Let be a constant satisfying the local Lipschitz condition (2.15), for instance the local Lipschitz constant . If is a coordinate-wise minimum of
then
where is the -th largest absolute value of the components of . That is, is an -stationary point.
The theorem places coordinate-wise minimality above -stationarity in the hierarchy of necessary optimality conditions for sparsity constrained problems, with the local constant in place of the global Lipschitz constant. Since every optimal solution of (P) is a CW-minimum, every optimal solution is an -stationary point.
Formalization Note The conclusion is the displayed condition (2.16). Its identification with -stationarity in the sense of Definition 2.3 goes through Lemma 2.2 and is not restated here. is universally quantified among constants satisfying (2.15). Assumption 2 is kept as on the page, although (2.15) is the hypothesis the proof uses. When , and the first line says on .
import Mathlib import Definitions.Def_SparseNLO_CWOpt_Setting
namespace SparseNLO.CWOpt
/-- Theorem 2.4 (p. 12): under Assumption 2, every CW-minimum `x*` of (P) satisfies (2.16):
`|∇_i f(x*)| ≤ L2 · M_s(x*)` for `i ∈ I₀(x*)` and `∇_i f(x*) = 0` for `i ∈ I₁(x*)`,
where `L2` is any constant satisfying the local Lipschitz condition (2.15). -/
theorem theorem_2_4 {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) :
(∀ i ∈ I0 xstar, |gradient f xstar i| ≤ L2 * Ms s xstar) ∧
(∀ i ∈ I1 xstar, gradient f xstar i = 0) := by sorry
end SparseNLO.CWOpt
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.