(2.10), p. 5 — f̂′_N(x, d) = N⁻¹ Σ_{j=1}^N h′_{ωʲ}(x, d)
ProvedSAARate.Sharp.display_2_10directional-derivativep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programming
Let with convex for every . For a sample with , let . Then for all ,
where and are the directional derivatives of and of at in direction .
This identity writes as a sample mean of i.i.d. variables, to which the strong law of large numbers applies in the proof of (2.6).
Formalization Note. The statement holds for every sample path, not only almost surely. The paper's is the Lean s (j-1).
Preamble
import Mathlib import Definitions.Def_SAARate_Sharp_Setting
Formal statement
namespace SAARate.Sharp
open MeasureTheory ProbabilityTheory Filter Topology
theorem display_2_10 {m : ℕ} {Ω : Type*} (h : E m → Ω → ℝ)
(hconv : ∀ ω, ConvexOn ℝ Set.univ (fun x => h x ω))
(s : ℕ → Ω) (N : ℕ) (hN : 1 ≤ N) (x d : E m) :
dirDeriv (saaObj h s N) x d =
(N : ℝ)⁻¹ * ∑ j ∈ Finset.range N, dirDeriv (fun y => h y (s j)) x d := by sorry
end SAARate.Sharp
Source
Shapiro & Homem-de-Mello, On Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs, preprint (SPEPS copy, edoc.hu-berlin.de), p. 5, proof of Proposition 2.2, (2.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.