Lemma 9, PDF p. 28 — after Algorithm 𝒜: Σ_{j∈J₁} b_j/μ_j ≤ √m and b_j ≤ β_j on J₂
ProvedAffinePolicies.SqrtBound.lemma_9affine-policiesalgorithm-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let , let for each , and consider any complete run of Algorithm with iterations and choices , with output and partition . Then for every ,
and for all .
The two properties are exactly what the affine policy of Theorem 4 needs: coordinates in are covered by the linear part of the policy at cost , and coordinates in are dominated by the fixed vector .
Formalization Note The statement holds for every run of the algorithm (the argmax choices are not unique). is the complement of . Positivity of , convexity, compactness and full-dimensionality of are not assumed.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_SqrtBound_Setting open Matrix
Formal statement
namespace AffinePolicies.SqrtBound
theorem lemma_9 {m : ℕ} (U : Set (Fin m → ℝ)) (hUnn : ∀ b ∈ U, 0 ≤ b)
(μ : Fin m → ℝ) (hμ : ∀ j, IsGreatest ((fun b : Fin m → ℝ => b j) '' U) (μ j))
(K : ℕ) (u : ℕ → Fin m → ℝ) (hrun : IsRun U μ K u) :
(∀ b ∈ U, scaledSum μ (J1 μ u K) b ≤ Real.sqrt m) ∧
∀ j, j ∉ J1 μ u K → ∀ b ∈ U, b j ≤ betaSum u K j := by sorry
end AffinePolicies.SqrtBound
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 9, PDF p. 28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.