(11), p. 5 — the first inequality of (7) with constant κ implies quasi-strong convexity (10) with constant κ
ProvedNecoaraNG.Chain.inclusion_11p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quasi-strong-convexitystrong-convexity
Let be closed and convex, let be convex on , differentiable at every point of , with -Lipschitz gradient on (), and assume the optimal set is nonempty. Let . If
then for every and ,
In class notation this is the inclusion , the first link of the chain (23).
Formalization Note is written . The standing assumptions of the paper are kept as hypotheses for uniformity with the other links of the chain, although the implication itself only uses that .
Preamble
import Mathlib import Definitions.Def_NecoaraNG_Chain_Setting
Formal statement
namespace NecoaraNG.Chain
open scoped InnerProductSpace
/-- (11), p. 5: the first inequality of (7) with constant `κ` implies (10) with constant `κ`. -/
theorem inclusion_11 {n : ℕ} (X : Set (E n)) (hXc : IsClosed X) (hXconv : Convex ℝ X)
(f : E n → ℝ) (hf : ConvexOn ℝ X f) (hdiff : ∀ x ∈ X, DifferentiableAt ℝ f x)
(Lf : ℝ) (hLf : 0 < Lf)
(hL : ∀ x ∈ X, ∀ y ∈ X, ‖gradient f x - gradient f y‖ ≤ Lf * ‖x - y‖)
(xstar : E n) (hxstar : xstar ∈ optSet X f) (κ : ℝ) (hκ : 0 < κ) :
StrongIneq X f κ → QuasiStrong X f κ := by sorry
end NecoaraNG.Chain
Source
Necoara, Nesterov & Glineur, Linear convergence of first order methods for non-strongly convex optimization, arXiv:1504.06298v4, p. 5, inclusion (11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.