Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, PART 1, p. 9 — SIˉ⊆S~IˉS_{\bar{\mathcal I}}\subseteq\widetilde S_{\bar{\mathcal I}}SIˉ​⊆SIˉ​

Proved
ScenarioExact.PartOne.subset_Stilde

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scenario-approach

Let X⊆Rd\mathcal X\subseteq\mathbb R^dX⊆Rd and Xδ⊆Rd\mathcal X_\delta\subseteq\mathbb R^dXδ​⊆Rd (δ∈Δ\delta\in\Deltaδ∈Δ) be convex, let c∈Rdc\in\mathbb R^dc∈Rd, and suppose that for every number kkk of constraints and every (δ(1),…,δ(k))∈Δk(\delta^{(1)},\dots,\delta^{(k)})\in\Delta^k(δ(1),…,δ(k))∈Δk the program PkP_kPk​ (minimise c⊤xc^\top xc⊤x over x∈X∩⋂iXδ(i)x\in\mathcal X\cap\bigcap_{i}\mathcal X_{\delta^{(i)}}x∈X∩⋂i​Xδ(i)​) has a unique solution xk∗x^*_kxk∗​. Fix m≥dm\ge dm≥d. Write SIˉS_{\bar{\mathcal I}}SIˉ​ for the set of multi-extractions (δ(1),…,δ(m))(\delta^{(1)},\dots,\delta^{(m)})(δ(1),…,δ(m)) whose support constraints are exactly δ(1),…,δ(d)\delta^{(1)},\dots,\delta^{(d)}δ(1),…,δ(d), and S~Iˉ\widetilde S_{\bar{\mathcal I}}SIˉ​ for the set where δ(d+1),…,δ(m)\delta^{(d+1)},\dots,\delta^{(m)}δ(d+1),…,δ(m) are not violated by the solution generated by δ(1),…,δ(d)\delta^{(1)},\dots,\delta^{(d)}δ(1),…,δ(d). Then

SIˉ⊆S~Iˉ.S_{\bar{\mathcal I}}\subseteq\widetilde S_{\bar{\mathcal I}}.SIˉ​⊆SIˉ​.

This is the first half of the fact, stated on p. 8 and proved at the end of PART 1 (p. 9), that SIˉS_{\bar{\mathcal I}}SIˉ​ and S~Iˉ\widetilde S_{\bar{\mathcal I}}SIˉ​ coincide up to a probability-zero set. It holds for every multi-extraction; no probability enters. The paper's step "the first ddd constraints are still the support constraints for the problem with m−1m-1m−1 constraints" uses Proposition 2.2 (at most ddd support constraints), which is why convexity is assumed.

Formalization Note. The paper leaves implicit that its Assumption 1 holds for every number of constraints; we state existence and uniqueness for every kkk and every sample, and take a solution family θs k ω assumed to solve PkP_kPk​ (so θs k ω is xk∗x^*_kxk∗​). Support constraints are the published IsSupportConstraint (removal admits a feasible point of strictly smaller cost), which under uniqueness is the paper's "its removal changes the solution". Closedness, measurability and full support are not needed and not assumed. Indexes are 0-based.

Preamble
import Mathlib
import Definitions.Def_ScenarioApproach_Generalization_violation
import Definitions.Def_ScenarioApproach_Generalization_scenarioProgram
import Definitions.Def_ScenarioApproach_Generalization_supportConstraint
import Definitions.Def_ScenarioExact_PartOne_Basic
open MeasureTheory ScenarioApproach.Generalization
open scoped ENNReal
Formal statement
namespace ScenarioExact.PartOne

/-- §3, PART 1, p. 9 (claim on p. 8): `S_𝓘̄ ⊆ S̃_𝓘̄`. Deterministic: for every multi-extraction
whose support constraints are exactly the first `d`, the solution generated by the first `d`
constraints violates none of the others. -/
theorem subset_Stilde {d m : ℕ} {Δ : Type*}
    (c : EuclideanSpace ℝ (Fin d)) (Θ : Set (EuclideanSpace ℝ (Fin d)))
    (Θδ : Δ → Set (EuclideanSpace ℝ (Fin d)))
    (hΘ_convex : Convex ℝ Θ) (hΘδ_convex : ∀ δ, Convex ℝ (Θδ δ))
    (hexu : ∀ (k : ℕ) (ω : Fin k → Δ), ∃! θ, IsSolution c Θ Θδ ω θ)
    (θs : (k : ℕ) → (Fin k → Δ) → EuclideanSpace ℝ (Fin d))
    (hθs : ∀ (k : ℕ) (ω : Fin k → Δ), IsSolution c Θ Θδ ω (θs k ω))
    (hm : d ≤ m) :
    S c Θ Θδ θs (Ibar d m) ⊆ Stilde Θδ θs hm := by sorry

end ScenarioExact.PartOne
Source
Campi & Garatti, The exact feasibility of randomized solutions of uncertain convex programs, SIAM J. Optim. 19(3) (2008); authors' final manuscript, p. 9, 'Proof of the fact that S_𝓘̄ = S̃_𝓘̄ up to a probability zero set', S_𝓘̄ ⊆ S̃_𝓘̄ (claim stated p. 8)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me