(3.21) — the subproblem step satisfies ⟨z,d⟩ + β‖d‖² ≤ 0
ProvedNestedSA.NASA.eq_3_21convex-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projection
Let be closed and convex, , , , and let be the step of subproblem (2.5), where . Then
This consequence of the optimality condition of (2.5) gives on , hence , and the bound used in Proposition 1.
Preamble
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_NestedSA_NASA_Basic open scoped RealInnerProductSpace
Formal statement
namespace NestedSA.NASA
/-- (3.21) (p. 11, proof of Lemma 4): for a closed convex `X` with Euclidean projection `P`, every `x ∈ X`, every
`z` and every `β > 0`, the step `d = ȳ(x, z, β) − x` satisfies `⟨z, d⟩ + β‖d‖² ≤ 0`. -/
theorem eq_3_21 {n : ℕ} (X : Set (EuclideanSpace ℝ (Fin n))) (hX_cl : IsClosed X) (hX_cvx : Convex ℝ X)
(P : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hP : SpectralProjGrad.Shared.IsProjOnto X P)
(x : EuclideanSpace ℝ (Fin n)) (hx : x ∈ X) (z : EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β) :
⟪z, ybar P x z β - x⟫ + β * ‖ybar P x z β - x‖ ^ 2 ≤ 0 := by sorry
end NestedSA.NASA
Source
Ghadimi, Ruszczyński, Wang, A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization, arXiv:1812.01094v2, §3, proof of Lemma 4, (3.21), p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.