Lemma 1, PDF p. 9 — on the instance ℐ of (6), z_Adapt(𝒰) ≤ 1
ProvedAffinePolicies.TwoGap.lemma_1adaptive-optimizationaffine-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let be an even natural number and consider the instance of (6): , , , and for , and . Then there is a feasible fully-adaptable solution of whose worst-case cost is at most , and consequently
This upper bound on the adaptive optimum is the adaptive side of the gap in Theorem 2.
Formalization Note The first conjunct (a feasible solution with worst-case cost at most ) is the solution the paper's proof constructs; stating it rules out the reading in which is because nothing is feasible. The condition of the instance is not used by the lemma and is dropped, which makes the statement stronger.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_TwoGap_Setting
Formal statement
namespace AffinePolicies.TwoGap
theorem lemma_1 (m : ℕ) (hm_even : Even m) :
(∃ (x : Fin m → ℝ) (y : (Fin m → ℝ) → Fin m → ℝ),
AffinePolicies.Simplex.Feasible (A6 m) (B6 m) (U6 m) x y ∧ AffinePolicies.Simplex.CostLE (c6 m) (d6 m) (U6 m) x y 1) ∧
AffinePolicies.Simplex.zAdapt (A6 m) (B6 m) (c6 m) (d6 m) (U6 m) ≤ 1 := by sorry
end AffinePolicies.TwoGap
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 1, PDF p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.