Proof of Theorem 3.1, p. 23 — in the instance of Theorem 3.1, z_Rob(b, d) ≥ 1
ProvedRobustPower.CostGap.robust_value_ge_onep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Consider the instance of Theorem 3.1: no first-stage variables (, so and ), continuous second-stage variables, a single constraint with and right-hand side in every scenario, and a cost map whose range is exactly the cube . Then the optimal value of the robust problem satisfies
This is the robust half of the gap in Theorem 3.1: the scenario with is among the scenarios, and the single robust decision must cover it.
Formalization Note is the extended-real infimum of (1.5); the statement does not assume that an optimal robust solution exists. No probability measure is involved.
Preamble
import Mathlib import Definitions.Def_RobustPower_CostGap_Problems open MeasureTheory Matrix
Formal statement
namespace RobustPower.CostGap
/-- Proof of Theorem 3.1, p. 23: in the instance of Theorem 3.1, `z_Rob(b, d) ≥ 1`. -/
theorem robust_value_ge_one {n : ℕ} (hn : 0 < n) {Ω : Type*}
(d : Ω → Fin n → ℝ) (hrange : Set.range d = Set.Icc 0 1) :
(1 : EReal) ≤
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
Source
Bertsimas & Goyal, On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems, authors' manuscript (MIT DSpace) of Math. Oper. Res. DOI 10.1287/moor.1090.0440, p. 23, proof of Theorem 3.1, display z_Rob(b, d) ≥ 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.