Theorem 3, proof, second Claim, PDF p. 23 — θ ≥ 1/3
ProvedAffinePolicies.LargeGap.claim_theta_geaffine-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let and , and consider the instance (19). Let , let have diagonal entries and off-diagonal entries , and let . If for some first-stage the affine policy is feasible and
then
This is the second parameter bound in the proof by contradiction of Theorem 3: the diagonal of the symmetric policy must carry most of the response to a unit demand .
Formalization Note As for the first Claim, the statement covers every symmetric feasible affine policy satisfying (27) rather than only the optimal one of Lemma 8; the hypotheses are jointly unsatisfiable by Theorem 3, as is inherent in a step of a proof by contradiction.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_LargeGap_Setting
Formal statement
namespace AffinePolicies.LargeGap
theorem claim_theta_ge (δ : ℝ) (hδ : 0 < δ) (m : ℕ) (hm : 200 < (m : ℝ) ^ δ)
(x : Fin m → ℝ) (μ θ lam : ℝ)
(hfeas : AffinePolicies.Simplex.Feasible (A19 m) (B19 m δ) (U19 m δ) x
(AffinePolicies.Simplex.affinePolicy (fun i j => if i = j then θ else μ) (fun _ => lam)))
(hcost : AffinePolicies.Simplex.CostLE (c19 m) (d19 m) (U19 m δ) x
(AffinePolicies.Simplex.affinePolicy (fun i j => if i = j then θ else μ) (fun _ => lam))
((m : ℝ) ^ ((1 : ℝ) / 2 - δ) / 4)) :
1 / 3 ≤ θ := 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, Theorem 3, proof, second Claim, PDF p. 23–24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.