Theorem 2 — fractional sorted-distance feasibility criterion
ProvedChenWasserstein.Reform.theorem_2Let be a finite-dimensional real normed space with its Borel sigma algebra, let , and let be arbitrary samples, with repetitions permitted. Let be open with nonempty complement . Write , , and , where is the infimum of the expected norm cost over all couplings. Assume .
At a fixed decision, take to be its safety set and let . Then the robust chance constraint is equivalent to the fractional sorted-distance inequality:
Here sums the smallest distances and adds the fractional remainder times the next distance. This criterion permits ties, unsafe samples, nonintegral , and equality at the threshold.
This is the intermediate feasibility criterion connecting the robust model to a finite array of distances.
Formalization Note The fixed decision is suppressed by using its set directly; no assumptions about the whole decision set or existence of an optimizer enter this pointwise assertion. The nonempty complement is the source's implicit nearest-point convention (F1). The published multiset order statistic replaces an explicit sorting permutation without changing multiplicities. The strict positive-radius assumption is retained; Remark 1 and F3 give a counterexample at radius zero.
import Mathlib import Definitions.Def_ChenWasserstein_Reform_Data open MeasureTheory open scoped ENNReal BigOperators
/- Imported declaration bodies, quoted verbatim for standalone blind auditing.
These are comments, not redeclarations or additional assumptions.
noncomputable def distUnsafe {E : Type*} [NormedAddCommGroup E] (S : Set E) (u : E) : ℝ :=
Metric.infDist u Sᶜ
noncomputable def kthSmallest {N : ℕ} (v : Fin N → ℝ) (j : ℕ) : ℝ :=
((Finset.univ.val.map v).sort (· ≤ ·)).getD j 0
def IsCoupling {S : Type*} [MeasurableSpace S] (μ₁ μ₂ : Measure S) (π : Measure (S × S)) : Prop :=
IsProbabilityMeasure π ∧ π.map Prod.fst = μ₁ ∧ π.map Prod.snd = μ₂
noncomputable def transportCost {S : Type*} [MeasurableSpace S] (c : S → S → ℝ)
(μ₁ μ₂ : Measure S) : ℝ≥0∞ :=
⨅ (π : Measure (S × S)) (_ : IsCoupling μ₁ μ₂ π), ∫⁻ p, ENNReal.ofReal (c p.1 p.2) ∂π
noncomputable def worstProb {S : Type*} [MeasurableSpace S] (c : S → S → ℝ) (μ : Measure S)
(δ : ℝ) (A : Set S) : ℝ≥0∞ :=
⨆ (P : Measure S) (_ : IsProbabilityMeasure P ∧ transportCost c μ P ≤ ENNReal.ofReal δ), P A
noncomputable def empiricalDistribution {E : Type*} [MeasurableSpace E] {N : ℕ}
(ξhat : Fin N → E) : Measure E :=
(N : ENNReal)⁻¹ • ∑ i, Measure.dirac (ξhat i)
noncomputable def fractionalSmallest {N : ℕ} (k : Fin N → ℝ) (ℓ : ℝ) : ℝ :=
(∑ j ∈ Finset.range (min ⌊ℓ⌋₊ N), WassDRCCP.Improved.kthSmallest k j) +
if ⌊ℓ⌋₊ < N then
(ℓ - (⌊ℓ⌋₊ : ℝ)) * WassDRCCP.Improved.kthSmallest k ⌊ℓ⌋₊ else 0
-/
namespace ChenWasserstein.Reform
/-- Chen, Kuhn and Wiesemann (2024), Theorem 2, (5), printed p. 414 / PDF p. 5.
Here S is the safety set S(x) at the fixed decision; no decision optimization is performed. -/
theorem theorem_2
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
[MeasurableSpace E] [BorelSpace E] {N : ℕ}
(ξ : Fin N → E) (S : Set E) (ε θ : ℝ)
(hN : 0 < N) (hε : 0 < ε) (hε1 : ε < 1) (hθ : 0 < θ)
(hS : IsOpen S) (hC : Sᶜ.Nonempty) :
ModelRiskOT.WorstProb.worstProb (fun u v : E => ‖u - v‖)
(WassersteinDRO.Duality.empiricalDistribution ξ) θ Sᶜ ≤ ENNReal.ofReal ε ↔
θ ≤ (1 / (N : ℝ)) *
fractionalSmallest (fun i => WassDRCCP.Improved.distUnsafe S (ξ i)) (ε * (N : ℝ)) := by sorry
end ChenWasserstein.Reform
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite-dimensional real normed vector space with its Borel σ-algebra, and is a natural number.
- are points of , is a set, and are real numbers.
Hypotheses.
- , and .
- is open, and is nonempty.
- No ordering is assumed on the samples.
Notation used in the conclusion.
- , and are these values sorted, with repeats kept.
- is the empirical measure.
- is the transport cost. The infimum is over probability measures on with marginals and , and its value lies in .
- The worst-case probability of the unsafe set is
Conclusion. Let , which lies strictly between and , and let , so that . Then
The comparison on the left is made in . No decision variable appears; and the samples are fixed.
Degenerate cases:
- , and . All are excluded.
- . Then , the sum is empty, and the right-hand side is .
- Many samples in the unsafe set. If at least of the samples lie in , then and the right-hand side is . Since , the right side of the equivalence is then false, and the statement asserts .
- Zero-dimensional . If , then , every , and the same applies.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.