Lemma 2.4 (c), p. 6 — under (2.13), A_N is a nonempty face of A
ProvedSAARate.Polyhedral.lemma_2_4_cAssume the conditions of Theorem 2.3: (i) is finite; (ii) every is piecewise linear and convex; (iii) is closed, convex and polyhedral; (iv) the set of optimal solutions of the true problem is nonempty and bounded. Assume also that every scenario has positive probability.
Then there are and points , chosen independently of the sample, such that
- form the set of extreme points of ;
- for every and ;
- for every sample path and every , if
then the set of optimal solutions of is nonempty and forms a face of .
The condition (2.13) involves only finitely many sample averages at fixed points, so the event that is a nonempty face of 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 among so that (2.13) never holds. (b) The paper writes ; here . The paper's proof first reduces to by adding an exact penalty , and its in clause 2 is the penalised function. For the unpenalised and (for example , ) no point satisfies clause 2, so cannot hold; when the existence of an outer point is not lost. (c) Every scenario is assumed to have positive mass (; p. 3 takes to be the support of ); the clause "for any realization" fails otherwise. (d) Indices are 0-based in Lean: is i.val < ℓ and is ℓ ≤ j.val in Fin q. "Extreme points" is Mathlib's Set.extremePoints, and clause 1 is an equality of sets.
import Mathlib import Definitions.Def_SAARate_Polyhedral_Setting open MeasureTheory ProbabilityTheory
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.