Theorem 1, p. 10 — ℙᴺ{V(x*_N) > ε(s*_N)} ≤ γ* with γ* the value of (10)
ProvedWaitJudge.Convex.theorem_1Let be the optimization variable, a cost vector, a convex domain, and convex constraint sets indexed by in a probability space . Ties are broken by minimising convex functions in succession. Let be an i.i.d. sample with , let be the solution of the scenario program
let be its number of support constraints, and let be the violation.
Let , , be any -valued function. Under Assumptions 1 and 2,
where is the value of the variational problem (10):
The theorem lets the user observe the number of support constraints after solving and then certify the solution at the level , with a confidence that holds uniformly over all convex problems and all distributions.
Formalization Note Assumption 1 is required for every sample (as on the page), Assumption 2 almost surely. The measurability the paper takes for granted (footnote 1) is assumed as two hypotheses: the set is measurable and every solution map is Borel measurable. is the paper's standing assumption (p. 2). The probability is compared with through ; .
import Mathlib import Definitions.Def_ScenarioApproach_Generalization_violation import Definitions.Def_WaitJudge_Convex_Setting open MeasureTheory ScenarioApproach.Generalization
namespace WaitJudge.Convex
theorem theorem_1 {d p : ℕ} {Δ : Type*} [MeasurableSpace Δ] (P : Measure Δ) [IsProbabilityMeasure P]
(c : E d) (X : Set (E d)) (Xδ : Δ → Set (E d)) (tb : Fin p → E d → ℝ)
(hX : Convex ℝ X) (hXδ : ∀ δ, Convex ℝ (Xδ δ))
(htb : ∀ j, ConvexOn ℝ Set.univ (tb j))
(hA1 : Assumption1 c X Xδ tb) (hA2 : Assumption2 c X Xδ tb P)
(hmeas : MeasurabilityPins c X Xδ tb)
(N : ℕ) (hN : d < N) (ε : ℕ → ℝ) (hε : ∀ k ≤ d, 0 ≤ ε k ∧ ε k ≤ 1) :
(Measure.pi fun _ : Fin N => P) {ω | ε (sstar c X Xδ tb ω) < violation P Xδ (xstar c X Xδ tb ω)} ≤ ENNReal.ofReal (gammaStar N d ε) := by sorry
end WaitJudge.Convex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.