(29), p. 10 — main inequality of the gradient mapping: f(y) ≥ f(x⁺) + ⟨g(x), y − x⟩ + ‖g(x)‖²/(2L_f)
ProvedNecoaraNG.ErrBound.gradient_mapping_29Under the standing assumptions of problem (P) — closed and convex, convex on and differentiable at every point of , Lipschitz on with constant , and an optimal solution exists — let , let be the projected gradient step and the gradient mapping. Then for every ,
This is the main property of the gradient mapping for convex functions with Lipschitz continuous gradient (Nesterov, Introductory Lectures on Convex Optimization, Theorem 2.2.7). Evaluated at suitable points of it drives the comparison between quadratic functional growth and the error bound.
Formalization Note The paper states (29) for all . Under its standing assumptions is only given on , so , and hence (29), only make sense for ; the statement is restricted to , which is all that Theorem 7 uses. No hypothesis on outside is added.
import Mathlib import Definitions.Def_NecoaraNG_ErrBound_Setting open scoped InnerProductSpace
namespace NecoaraNG.ErrBound
theorem gradient_mapping_29 {n : ℕ} (X : Set (NecoaraNG.Chain.E n)) (hXc : IsClosed X) (hXconv : Convex ℝ X)
(f : NecoaraNG.Chain.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 : NecoaraNG.Chain.E n) (hxstar : xstar ∈ NecoaraNG.Chain.optSet X f) :
∀ x ∈ X, ∀ xp, IsPGStep X f Lf x xp → ∀ y ∈ X,
f xp + ⟪Lf • (x - xp), y - x⟫_ℝ + 1 / (2 * Lf) * ‖Lf • (x - xp)‖ ^ 2 ≤ f y := by sorry
end NecoaraNG.ErrBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.