Proposition 1 (ii), p. 6 — all limit points of {x*_n} lie in X*, w.p.1
ProvedSolutionQuality.SRP.prop1_iiconsistencyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programming
Assume (A1)–(A3), and let be i.i.d. as . Let be an optimal solution of (SP) built on , for each , and let be the set of optimal solutions of (SP). Then, with probability one, every limit point (cluster point) of the sequence belongs to :
When (SP) has several optimal solutions the sequence need not converge, but it accumulates only at optimal solutions. This is part (ii) of Proposition 1 and is used in part (iii).
Formalization Note. is not used and is dropped. Each is a measurable map that, almost surely, lies in and minimizes the sample mean over on the same first observations. A limit point is a MapClusterPt of the sequence along atTop.
Preamble
import Mathlib import Definitions.Def_SolutionQuality_SRP_Setting
Formal statement
namespace SolutionQuality.SRP
open MeasureTheory ProbabilityTheory Filter
theorem prop1_ii {d : ℕ} {Ξ : Type*} [MeasurableSpace Ξ]
(μ : Measure Ξ) [IsProbabilityMeasure μ]
(f : E d → Ξ → ℝ) (hfm : ∀ x, Measurable (f x))
(X : Set (E d)) (hA : Assumptions μ f X)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ξ : ℕ → Ω → Ξ) (hξ : IsIIDSample P μ ξ)
(xn : ℕ → Ω → E d) (hxn : IsSAAMinimizerSeq P f X ξ xn) :
∀ᵐ ω ∂P, ∀ x, MapClusterPt x atTop (fun n => xn n ω) → x ∈ optSet μ f X := by sorry
end SolutionQuality.SRP
Source
Bayraksan & Morton, Assessing Solution Quality in Stochastic Programs, preprint (January 26, 2005), p. 6, Proposition 1 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.