Theorem 2.1, p. 5 — at a sharp minimum x̄, w.p.1 for N large enough the SAA problem has the unique optimal solution x̂_N = x̄
ProvedSAARate.Sharp.theorem_2_1Let be a probability measure on , and , and consider the true problem and its sample average approximation
where is an i.i.d. sample from . Suppose that
- for every the function is convex;
- the expected value function is well defined and finite valued;
- the set is closed and convex;
- Assumption (A) holds: is the unique optimal solution of the true problem, and for some , for all .
Then w.p.1 for large enough the approximating problem has a unique optimal solution and :
"W.p.1 for large enough" means: for almost every sample path there is , depending on the path, such that the statement holds for every . At a sharp minimum, therefore, the Monte Carlo approximation does not merely converge to the true solution: it returns it exactly once the sample is large enough.
Formalization Note. Assumption 2 is encoded as integrability of for every . The sample is one i.i.d. sequence on an auxiliary probability space , and uses its first terms; the conclusion is "for -almost every path, eventually in ". "Unique optimal solution equal to " is the set equality , which includes existence.
import Mathlib import Definitions.Def_SAARate_Sharp_Setting
namespace SAARate.Sharp
open MeasureTheory ProbabilityTheory Filter Topology
theorem theorem_2_1 {m : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (h : E m → Ω → ℝ)
(hconv : ∀ ω, ConvexOn ℝ Set.univ (fun x => h x ω))
(hint : ∀ x, Integrable (h x) P)
(Θ : Set (E m)) (hΘc : IsClosed Θ) (hΘv : Convex ℝ Θ)
(xbar : E m) (hA : AssumptionA P h Θ xbar)
{S : Type*} [MeasurableSpace S] (Q : Measure S) [IsProbabilityMeasure Q]
(ω : ℕ → S → Ω) (hω : IsIIDSample Q P ω) :
∀ᵐ s ∂Q, ∀ᶠ N in atTop, argminOn (saaObj h (fun j => ω j s) N) Θ = {xbar} := by sorry
end SAARate.Sharp
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.