Equations (5.3)–(5.4) — cost of the doubled solution
ProvedRobustPower.AdaptGap.eq_5_3_5_4_cost_boundadaptive-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
In the nonnegative symmetric scenario model, let be any feasible adaptive decision and let realize the point of symmetry. The worst-case cost of the doubled static decision is bounded by four times the worst-case cost of the original adaptive decision:
This estimate supplies the explicit factor four in Theorem 5.1 and applies to every feasible adaptive decision, without an attainment assumption.
Preamble
import Mathlib import Definitions.Def_RobustPower_AdaptGap_Problems
Formal statement
namespace RobustPower.AdaptGap
/-- Inequalities (5.3)–(5.4), p. 29, for every feasible adaptive solution. -/
theorem eq_5_3_5_4_cost_bound {m n₁ n₂ : ℕ} {Ω : Type*}
(A : Matrix (Fin m) (Fin n₁) ℝ) (B : Matrix (Fin m) (Fin n₂) ℝ)
(b : Ω → Fin m → ℝ) (c : Fin n₁ → ℝ) (d : Ω → Fin n₂ → ℝ)
(I₁ : Set (Fin n₁)) (I₂ : Set (Fin n₂))
(x : Fin n₁ → ℝ) (y : Ω → Fin n₂ → ℝ) (ω₀ : Ω)
(hc : 0 ≤ c) (hb : ∀ ω, 0 ≤ b ω) (hd : ∀ ω, 0 ≤ d ω)
(hfeas : AdaptFeasible A B b I₁ I₂ x y)
(hcenter : RobustPower.StochGap.IsSymmetricAbout (scenarioSet b d) (b ω₀, d ω₀)) :
robCost c d ((2 : ℝ) • x) ((2 : ℝ) • y ω₀) ≤
(4 : EReal) * adaptCost c d x y := by sorry
end RobustPower.AdaptGap
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. 29, (5.3)–(5.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.