Theorem 3.1 — with uniform hypercube cost uncertainty, z_Rob(b, d) ≥ (n + 1) · z_Stoch(b, d)
ProvedRobustPower.CostGap.theorem_3_1_cost_uncertainty_gapConsider the instances of the stochastic problem and the robust problem with no first-stage variables (, so and ), continuous second-stage variables (), and a single constraint () with . The right-hand side is in every scenario, so the constraint reads . Let be a probability space of scenarios and a measurable cost map such that
- the uncertainty set is , that is, the range of is exactly the cube ;
- the coordinates are independent and each uniformly distributed on under .
Then
The uncertainty set and the measure are both symmetric and there are no integer variables: these are the hypotheses under which, for right-hand-side uncertainty alone, the robust optimum is at most twice the stochastic one (Theorem 2.1). Theorem 3.1 shows that this bound fails once the costs are uncertain: the stochasticity gap grows linearly in the dimension.
Formalization Note Both optimal values are infima in the extended reals, the stochastic problem ranges over integrable policies whose constraints hold in every scenario, and neither problem is assumed to have an optimal solution. The hypothesis is implicit in the paper. Independence and uniformity are stated as: the law of under equals the product of uniform distributions on .
import Mathlib import Definitions.Def_RobustPower_CostGap_Problems open MeasureTheory Matrix
namespace RobustPower.CostGap
/-- Theorem 3.1 (p. 22). The instance `n₁ = 0`, `n₂ = n`, `p₂ = 0`, `m = 1`, `c = 0`, `A = 0`,
`B = [1, …, 1]`, `b(ω) = 1`, with uncertainty set `{1} × [0, 1]ⁿ` and the coordinates of `d`
independent and uniform on `[0, 1]`, has `z_Rob(b, d) ≥ (n + 1) · z_Stoch(b, d)`. -/
theorem theorem_3_1_cost_uncertainty_gap {n : ℕ} (hn : 0 < n)
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(d : Ω → Fin n → ℝ) (hd : Measurable d) (hrange : Set.range d = Set.Icc 0 1)
(hlaw : μ.map d = Measure.pi (fun _ : Fin n => volume.restrict (Set.Icc (0 : ℝ) 1))) :
(((n : ℝ) + 1 : ℝ) : EReal) *
zStochBD μ (0 : Matrix (Fin 1) (Fin 0) ℝ) (fun _ _ => 1 : Matrix (Fin 1) (Fin n) ℝ)
(fun _ _ => 1 : Ω → Fin 1 → ℝ) (0 : Fin 0 → ℝ) d ∅ ∅ ≤
zRobBD (0 : Matrix (Fin 1) (Fin 0) ℝ) (fun _ _ => 1 : Matrix (Fin 1) (Fin n) ℝ)
(fun _ _ => 1 : Ω → Fin 1 → ℝ) (0 : Fin 0 → ℝ) d ∅ ∅ := by sorry
end RobustPower.CostGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.