Lemma 10, PDF p. 29 — Algorithm 𝒜 executes at most 2√m iterations
ProvedAffinePolicies.SqrtBound.lemma_10affine-policiesalgorithm-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let , let and assume for every . If iterations of Algorithm are executed (each with the loop test satisfied and a maximizing choice ), then
In particular the number of iterations of a complete run is at most , and the algorithm terminates. The bound is used in the proof of Theorem 4 to show that .
Formalization Note The statement is made for every executed prefix of iterations, without the stopping test; this is stronger than the paper's statement about the number of iterations of a finished run, and it is what yields termination. Nonnegativity, convexity and compactness of are not assumed.
Preamble
import Mathlib import Definitions.Def_AffinePolicies_SqrtBound_Setting open Matrix
Formal statement
namespace AffinePolicies.SqrtBound
theorem lemma_10 {m : ℕ} (U : Set (Fin m → ℝ))
(μ : Fin m → ℝ) (hμ : ∀ j, IsGreatest ((fun b : Fin m → ℝ => b j) '' U) (μ j))
(hμpos : ∀ j, 0 < μ j)
(K : ℕ) (u : ℕ → Fin m → ℝ) (hiter : ∀ k < K, IsIteration U μ u k) :
(K : ℝ) ≤ 2 * Real.sqrt m := 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 10, PDF p. 29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.