Theorem 4.3, p. 13 — DRS residuals vanish at rate o(1/√k); u^k, v^k share stationary cluster points with φ = lim φ^DR_γ(s^k); level-bounded φ gives bounded iterates
ProvedNonconvexDRS.DRS.theorem_4_3Suppose Assumption I holds: is -smooth () and -hypoconvex with , is proper and lower semicontinuous, and has a minimizer. Let the stepsize and relaxation lie in the ranges of Theorem 4.1: either and , or , and , with and . Let be any sequence generated by DRS,
from an arbitrary . Then:
- the residual vanishes with rate ;
- and have the same cluster points; every such cluster point is stationary for , i.e. ; and the limit exists, is finite, and equals for every cluster point ;
- if is level bounded, then , and are bounded.
This is the paper's convergence result for nonconvex DRS: it holds for every relaxation and, when is strongly convex, beyond , under stepsize bounds that Theorem 4.7 shows to be tight.
Formalization Note Rate (i) is . "Stationary" is in the regular (Fréchet) subdifferential of as an -valued function, which is what the proof establishes and is stronger than limiting stationarity. Cluster points are MapClusterPt points. The page's closing sentence of (ii), "In fact, for each one has ", is false as printed (for , the distance is ) and is not part of this statement; the separate item theorem_4_3_ii_dist states it with the constant . Reciprocal bounds are multiplied out. The added hypothesis is needed for ; makes affine. No a-priori decrease, summability or boundedness is assumed.
import Mathlib import Definitions.Def_NonconvexSplitting_Shared_LimitingSubdiff import Definitions.Def_NonconvexDRS_DRS_Setting open NonconvexSplitting.Shared open Filter Topology open scoped InnerProductSpace
namespace NonconvexDRS.DRS
/-- Theorem 4.3 (Subsequential convergence), p. 13, without the "In fact" sentence of (ii)
(see `theorem_4_3_ii_dist`). -/
theorem theorem_4_3 {p : ℕ} (φ₁ : EuclideanSpace ℝ (Fin p) → ℝ) (φ₂ : EuclideanSpace ℝ (Fin p) → EReal)
(L σ : ℝ) (hL : 0 < L) (hσ : -L ≤ σ ∧ σ ≤ L)
(hsmooth : IsLSmooth φ₁ L) (hhypo : IsHypoconvex φ₁ σ)
(hprop : IsProper φ₂) (hlsc : LowerSemicontinuous φ₂)
(hsol : ∃ xs, ∀ x, (φ₁ xs : EReal) + φ₂ xs ≤ (φ₁ x : EReal) + φ₂ x)
(γ lam : ℝ) (hγ : 0 < γ) (hrange : StepRange L σ γ lam)
(s u v : ℕ → EuclideanSpace ℝ (Fin p)) (hrun : IsDRSRun φ₁ φ₂ γ lam s u v) :
Tendsto (fun k : ℕ => Real.sqrt (k : ℝ) *
(Finset.range (k + 1)).inf' Finset.nonempty_range_add_one (fun i => ‖u i - v i‖))
atTop (𝓝 0) ∧
({y | MapClusterPt y atTop u} = {y | MapClusterPt y atTop v} ∧
(∀ y, MapClusterPt y atTop u → IsRegularSubgrad (phi φ₁ φ₂) y 0) ∧
∃ φstar : ℝ, Tendsto (fun k => dre φ₁ φ₂ γ (s k)) atTop (𝓝 (φstar : EReal)) ∧
∀ y, MapClusterPt y atTop u → phi φ₁ φ₂ y = φstar) ∧
(LevelBounded (phi φ₁ φ₂) →
Bornology.IsBounded (Set.range s) ∧ Bornology.IsBounded (Set.range u) ∧
Bornology.IsBounded (Set.range v)) := by sorry
end NonconvexDRS.DRS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.