Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.4 (c), p. 6 — under (2.13), A_N is a nonempty face of A

Proved
SAARate.Polyhedral.lemma_2_4_c

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

facesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedralsample-average-approximationstochastic-programming

Assume the conditions of Theorem 2.3: (i) Ω\OmegaΩ is finite; (ii) every h(⋅,ω)h(\cdot,\omega)h(⋅,ω) is piecewise linear and convex; (iii) Θ\ThetaΘ is closed, convex and polyhedral; (iv) the set AAA of optimal solutions of the true problem min⁡x∈Θf(x)\min_{x\in\Theta}f(x)minx∈Θ​f(x) is nonempty and bounded. Assume also that every scenario has positive probability.

Then there are q≥ℓq\ge\ellq≥ℓ and points x1,…,xq∈Rmx_1,\dots,x_q\in\mathbb R^mx1​,…,xq​∈Rm, chosen independently of the sample, such that

  1. x1,…,xℓx_1,\dots,x_\ellx1​,…,xℓ​ form the set of extreme points of AAA;
  2. f(xi)<f(xj)f(x_i)<f(x_j)f(xi​)<f(xj​) for every i∈{1,…,ℓ}i\in\{1,\dots,\ell\}i∈{1,…,ℓ} and j∈{ℓ+1,…,q}j\in\{\ell+1,\dots,q\}j∈{ℓ+1,…,q};
  3. for every sample path and every NNN, if
f^N(xi)<f^N(xj)for all i∈{1,…,ℓ}, j∈{ℓ+1,…,q},(2.13)\hat f_N(x_i)<\hat f_N(x_j)\quad\text{for all } i\in\{1,\dots,\ell\},\ j\in\{\ell+1,\dots,q\},\tag{2.13}f^​N​(xi​)<f^​N​(xj​)for all i∈{1,…,ℓ}, j∈{ℓ+1,…,q},(2.13)

then the set ANA_NAN​ of optimal solutions of min⁡x∈Θf^N(x)\min_{x\in\Theta}\hat f_N(x)minx∈Θ​f^​N​(x) is nonempty and forms a face of AAA.

The condition (2.13) involves only finitely many sample averages at fixed points, so the event that ANA_NAN​ is a nonempty face of AAA is controlled by finitely many one-dimensional deviations. This is the deterministic core of Theorems 2.3 and 3.2.

Formalization Note (a) Clause 2 is not in the printed statement of (c); the proof of Theorem 3.2 (p. 12) recalls it, and the second proof of Theorem 2.3 (p. 8) uses it. Without it the statement would be trivially satisfiable, by repeating an extreme point of AAA among xℓ+1,…,xqx_{\ell+1},\dots,x_qxℓ+1​,…,xq​ so that (2.13) never holds. (b) The paper writes ℓ<q\ell<qℓ<q; here ℓ≤q\ell\le qℓ≤q. The paper's proof first reduces to Θ=Rm\Theta=\mathbb R^mΘ=Rm by adding an exact penalty α dist1(x,Θ)\alpha\,\mathrm{dist}_1(x,\Theta)αdist1​(x,Θ), and its fff in clause 2 is the penalised function. For the unpenalised fff and Θ=A\Theta=AΘ=A (for example h≡0h\equiv0h≡0, Θ=[0,1]\Theta=[0,1]Θ=[0,1]) no point xjx_jxj​ satisfies clause 2, so ℓ<q\ell<qℓ<q cannot hold; when Θ≠A\Theta\ne AΘ=A the existence of an outer point is not lost. (c) Every scenario is assumed to have positive mass (P{ω}≠0P\{\omega\}\ne0P{ω}=0; p. 3 takes Ω\OmegaΩ to be the support of PPP); the clause "for any realization" fails otherwise. (d) Indices are 0-based in Lean: {1,…,ℓ}\{1,\dots,\ell\}{1,…,ℓ} is i.val < ℓ and {ℓ+1,…,q}\{\ell+1,\dots,q\}{ℓ+1,…,q} is ℓ ≤ j.val in Fin q. "Extreme points" is Mathlib's Set.extremePoints, and clause 1 is an equality of sets.

Preamble
import Mathlib
import Definitions.Def_SAARate_Polyhedral_Setting

open MeasureTheory ProbabilityTheory
Formal statement
namespace SAARate.Polyhedral

/-- Lemma 2.4 (c), p. 6, with the gap `f(x_i) < f(x_j)` recalled on p. 12: under (i)–(iv)
there are finitely many points `x_1, …, x_q`, independent of the sample, whose first `ℓ` form
the set of extreme points of `A`, with `f(x_i) < f(x_j)` for `i ≤ ℓ < j`, and such that for
every sample path and every `N`, condition (2.13) forces `A_N` to be nonempty and a face of `A`.
Indices are 0-based: the paper's `{1, …, ℓ}` is `i.val < ℓ`, its `{ℓ+1, …, q}` is `ℓ ≤ j.val`.
`hP` (every scenario has positive mass, p. 3) is a disclosed pin; the paper's `ℓ < q` is
`ℓ ≤ q` here (see the Formalization Note). -/
theorem lemma_2_4_c {m : ℕ} {Ω : Type*} [Fintype Ω] [MeasurableSpace Ω]
    [MeasurableSingletonClass Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (hP : ∀ ω, P {ω} ≠ 0)
    (h : SAARate.Sharp.E m → Ω → ℝ) (hpl : ∀ ω, IsPLConvex (fun x => h x ω))
    (Θ : Set (SAARate.Sharp.E m)) (hΘc : IsClosed Θ) (hΘv : Convex ℝ Θ) (hΘp : IsPolyhedral Θ)
    (hA : (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ).Nonempty ∧
      Bornology.IsBounded (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ)) :
    ∃ (q ℓ : ℕ), ℓ ≤ q ∧ ∃ x : Fin q → SAARate.Sharp.E m,
      {y | ∃ i : Fin q, i.val < ℓ ∧ x i = y} =
          Set.extremePoints ℝ (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ) ∧
        (∀ i j : Fin q, i.val < ℓ → ℓ ≤ j.val →
          SAARate.Sharp.expectedObj P h (x i) < SAARate.Sharp.expectedObj P h (x j)) ∧
        ∀ (s : ℕ → Ω) (N : ℕ),
          (∀ i j : Fin q, i.val < ℓ → ℓ ≤ j.val → SAARate.Sharp.saaObj h s N (x i) < SAARate.Sharp.saaObj h s N (x j)) →
            (SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h s N) Θ).Nonempty ∧
              IsFace (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ) (SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h s N) Θ) := by sorry

end SAARate.Polyhedral
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. 6, Lemma 2.4 (c), (2.13); p. 12, proof of Theorem 3.2 (f(x_i) < f(x_j)); p. 3, (2.1) for the finite support
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 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