Proof of Theorem 4, (48)–(55), PDF pp. 30–31 — the affine solution x̃ = 3√m x*, ỹ(b) is feasible
ProvedAffinePolicies.SqrtBound.constructed_feasibleaffine-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Assume and . Let , let satisfy , and take any complete run of Algorithm with iterations, choices and final index set . Let be any feasible solution of . Define
Then is feasible for : and, for every , and .
This is the first half of the proof of Theorem 4; is an affine policy.
Formalization Note The paper starts from an optimal ; the statement is made for every feasible one, which is stronger and avoids assuming that an optimum is attained. When , (the empty sum). Only and of the standing assumptions are used; is assumed (it follows from full-dimensionality, see the milestone on (38)).
Preamble
import Mathlib import Definitions.Def_AffinePolicies_SqrtBound_Setting open Matrix
Formal statement
namespace AffinePolicies.SqrtBound
theorem constructed_feasible {m n₁ n₂ : ℕ} (A : Matrix (Fin m) (Fin n₁) ℝ)
(B : Matrix (Fin m) (Fin n₂) ℝ) (U : Set (Fin m → ℝ))
(hA : ∀ i j, 0 ≤ A i j) (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) :
AffinePolicies.Simplex.Feasible A B U ((3 * Real.sqrt m) • xs)
(AffinePolicies.Simplex.affinePolicy (thmPolicyP ys bstar μ (J1 μ u K)) (thmPolicyq ys u K)) := 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, (48)–(55), PDF pp. 30–31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.