Proof of Theorem 3, p. 8 — the projection onto X* is constant along the segment from x̄ to x
ProvedNecoaraNG.Chain.proj_segmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projectionquasi-strong-convexity
Let be convex, let be convex on , and let contain a point . Let and let be a nearest point of to . Then for every , is also a nearest point of to :
This is the fact used in the proofs of Theorems 1 and 3: along the segment the projection onto the optimal set does not move, so (10) or (17) can be applied at every point of the segment with the same .
Formalization Note The conclusion is stated with the nearest-point predicate: and for all . The hypotheses on and are the paper's standing ones (they make convex); the closedness of and the Lipschitz gradient are not needed and are omitted.
Preamble
import Mathlib import Definitions.Def_NecoaraNG_Chain_Setting
Formal statement
namespace NecoaraNG.Chain
open scoped InnerProductSpace
/-- Projection invariance along the segment `[x̄, x]` (proof of Theorem 3, p. 8):
if `x̄ = [x]_{X*}` then `[x̄ + t (x - x̄)]_{X*} = x̄` for every `t ∈ [0, 1]`. -/
theorem proj_segment {n : ℕ} (X : Set (E n)) (hXconv : Convex ℝ X)
(f : E n → ℝ) (hf : ConvexOn ℝ X f) (xstar : E n) (hxstar : xstar ∈ optSet X f) :
∀ x ∈ X, ∀ xbar, IsNearest (optSet X f) x xbar →
∀ t ∈ Set.Icc (0 : ℝ) 1, IsNearest (optSet X f) (xbar + t • (x - xbar)) xbar := by sorry
end NecoaraNG.Chain
Source
Necoara, Nesterov & Glineur, Linear convergence of first order methods for non-strongly convex optimization, arXiv:1504.06298v4, p. 8, proof of Theorem 3, sentence after the display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.