Lemma 4, PDF p. 17 — for the instance ℐ of (19), z_Adapt(𝒰) ≤ 1
ProvedAffinePolicies.LargeGap.lemma_4adaptive-optimizationaffine-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let and let satisfy (condition (18)). For the instance of (19) — , , , with unit diagonal and off-diagonal entries , and the convex hull of , the unit vectors , and the vectors with — there is a feasible fully-adaptable solution whose worst-case cost is at most ; consequently
This upper bound on the fully-adaptable optimum is one half of the large gap of Theorem 3.
Formalization Note The existence of a feasible solution of cost at most is stated explicitly, so that the bound is not satisfied by the junk value of an empty infimum. The paper's own witness ( at and at the other generators) relies on , i.e. ; the statement is kept for every , as on the page.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_LargeGap_Setting
Formal statement
namespace AffinePolicies.LargeGap
theorem lemma_4 (δ : ℝ) (hδ : 0 < δ) (m : ℕ) (hm : 200 < (m : ℝ) ^ δ) :
(∃ (x : Fin m → ℝ) (y : (Fin m → ℝ) → Fin m → ℝ),
AffinePolicies.Simplex.Feasible (A19 m) (B19 m δ) (U19 m δ) x y ∧ AffinePolicies.Simplex.CostLE (c19 m) (d19 m) (U19 m δ) x y 1) ∧
AffinePolicies.Simplex.zAdapt (A19 m) (B19 m δ) (c19 m) (d19 m) (U19 m δ) ≤ 1 := by sorry
end AffinePolicies.LargeGap
Source
Bertsimas & Goyal, On the power and limitations of affine policies in two-stage adaptive optimization, Math. Program. Ser. A, DOI 10.1007/s10107-011-0444-4, Lemma 4, PDF p. 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.