Proof of Theorem 4, (56)–(59), PDF pp. 31–32 — the affine solution costs at most 3√m times the adaptive one
ProvedAffinePolicies.SqrtBound.constructed_cost_leaffine-policiesapproximation-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Assume and . With , , a complete run , of Algorithm , and a feasible solution of as in the feasibility milestone, let and with . If bounds the worst-case cost of , that is for all , then
Applied with approaching this is the bound of the paper.
Formalization Note Stated for every feasible and every cost bound , rather than for an optimal solution and ; this avoids assuming attainment. Neither nor is needed and neither is assumed; is assumed.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_SqrtBound_Setting open Matrix
Formal statement
namespace AffinePolicies.SqrtBound
theorem constructed_cost_le {m n₁ n₂ : ℕ} (A : Matrix (Fin m) (Fin n₁) ℝ)
(B : Matrix (Fin m) (Fin n₂) ℝ) (c : Fin n₁ → ℝ) (d : Fin n₂ → ℝ) (U : Set (Fin m → ℝ))
(hd : 0 ≤ d) (hUnn : ∀ b ∈ U, 0 ≤ b)
(μ : Fin m → ℝ) (hμ : ∀ j, IsGreatest ((fun b : Fin m → ℝ => b j) '' U) (μ j))
(hμpos : ∀ j, 0 < μ j)
(bstar : Fin m → Fin m → ℝ) (hbstar : ∀ j, bstar j ∈ U ∧ bstar j j = μ j)
(K : ℕ) (u : ℕ → Fin m → ℝ) (hrun : IsRun U μ K u)
(xs : Fin n₁ → ℝ) (ys : (Fin m → ℝ) → Fin n₂ → ℝ) (hfs : AffinePolicies.Simplex.Feasible A B U xs ys) :
∀ t : ℝ, AffinePolicies.Simplex.CostLE c d U xs ys t →
AffinePolicies.Simplex.CostLE c d U ((3 * Real.sqrt m) • xs)
(AffinePolicies.Simplex.affinePolicy (thmPolicyP ys bstar μ (J1 μ u K)) (thmPolicyq ys u K))
(3 * Real.sqrt m * t) := 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, Proof of Theorem 4, (56)–(59), PDF pp. 31–32
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.