Lemma 7, PDF p. 19 — permuting an optimal affine solution, y^σ(b) = P^σ b + q^σ, keeps it optimal
ProvedAffinePolicies.LargeGap.lemma_7affine-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimizationsymmetry
Let , , and consider the instance (19). Let with be an optimal affine solution, and let be a permutation of . Define
Then with
is also an optimal affine solution of the same instance. Note that is not the vector with its coordinates permuted.
This is the step that makes the set of optimal affine solutions closed under the action of ; averaging over that action (Lemma 8) produces a symmetric optimum.
Formalization Note The page writes ; the symmetric group meant is (the indices run over ). The first-stage decision is kept unchanged; since and it plays no role. Optimality is with respect to the worst-case cost over among all feasible affine solutions. No threshold on is needed.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_LargeGap_Setting
Formal statement
namespace AffinePolicies.LargeGap
theorem lemma_7 (δ : ℝ) (m : ℕ) (σ : Equiv.Perm (Fin m)) (x : Fin m → ℝ)
(P : Matrix (Fin m) (Fin m) ℝ) (q : Fin m → ℝ)
(hopt : AffinePolicies.Simplex.IsOptimalAff (A19 m) (B19 m δ) (c19 m) (d19 m) (U19 m δ) x P q) :
AffinePolicies.Simplex.IsOptimalAff (A19 m) (B19 m δ) (c19 m) (d19 m) (U19 m δ) x
(P.submatrix σ σ) (q ∘ σ) := 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 7, PDF p. 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.