Eq. (5.14) — the robust cost of is at most the adaptive cost
ProvedRobustPower.Hypercube.eq_5_14_corner_cost_le_adapt_costadaptive-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
In the setting of (5.6)–(5.7), with for every scenario, let satisfy entrywise for every . If is feasible for , then
The left side is the worst-case cost in of the static pair ; the right side is the worst-case cost in of .
Formalization Note Both costs are extended reals; the inequality is in .
Preamble
import Definitions.Def_RobustPower_Hypercube_Problems
Formal statement
namespace RobustPower.Hypercube
/-- Inequality (5.14) and the chain around it (p. 32): let `ω̄` be a scenario whose
cost vector `d(ω̄)` is entrywise maximal over `Ω`. For every feasible solution
`(x, y(·))` of `Π_Adapt(A,B,b,d)`, the worst-case cost of the static pair `(x, y(ω̄))`,
`cᵀx + max_ω d(ω)ᵀy(ω̄)`, is at most `cᵀx + max_ω d(ω)ᵀy(ω)`. -/
theorem eq_5_14_corner_cost_le_adapt_cost
{m n₁ n₂ : ℕ} {Ω : Type*}
(A : Ω → Matrix (Fin m) (Fin n₁) ℝ)
(B : Ω → Matrix (Fin m) (Fin n₂) ℝ)
(b : Ω → Fin m → ℝ)
(I₁ : Set (Fin n₁)) (I₂ : Set (Fin n₂))
(c : Fin n₁ → ℝ) (d : Ω → Fin n₂ → ℝ)
(hd : ∀ ω, 0 ≤ d ω)
(ωbar : Ω) (hdbar : ∀ ω j, d ω j ≤ d ωbar j)
(x : Fin n₁ → ℝ) (y : Ω → Fin n₂ → ℝ)
(hxy : adaptFeasible A B b I₁ I₂ x y) :
RobustPower.AdaptGap.robCost c d x (y ωbar) ≤ RobustPower.AdaptGap.adaptCost c d x y := by sorry
end RobustPower.Hypercube
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. 32, Eq. (5.14) and the chain containing it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.