Theorem 3, proof, third Claim, PDF p. 24 — −1/m^{1+δ/2} ≤ μ < 0
ProvedAffinePolicies.LargeGap.claim_mu_boundsaffine-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 third parameter bound in the proof by contradiction of Theorem 3; combined with the first two, it forces the cost at above .
Formalization Note As for the other Claims, the statement covers every symmetric feasible affine policy satisfying (27); 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_mu_bounds (δ : ℝ) (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 / (m : ℝ) ^ (1 + δ / 2)) ≤ μ ∧ μ < 0 := 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, third Claim, PDF p. 24–25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.