Proof of Theorem 2.2, p. 586 — for and
ProvedMinimaxSLP.ObjExtremal.Qval_homogeneous_superadditivelinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1second-stage-value
Let be such that , and assume for all (Assumption 3). Then the second-stage value is positively homogeneous and superadditive in :
- for every and ;
- for all ,
In the proof of Theorem 2.2 these give .
Formalization Note The paper's display is the case , ; the statement here is the general form.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_ObjExtremal_Model open MeasureTheory Matrix Filter Topology
Formal statement
namespace MinimaxSLP.ObjExtremal
/-- Proof of Theorem 2.2 (p. 586): `𝒬(·, x)` is positively homogeneous,
`𝒬(t q, x) = t 𝒬(q, x)` for `t > 0`, and superadditive,
`𝒬(a + b, x) ≥ 𝒬(a, x) + 𝒬(b, x)` (the paper's display is the case
`a = v_k/v_k0`, `b = r_k/√ε`). -/
theorem Qval_homogeneous_superadditive {n r d : ℕ}
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (h : Fin r → ℝ)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(x : Fin n → ℝ) (hrec : (MinimaxSLP.ObjSDP.recourseSet W T h x).Nonempty) :
(∀ t : ℝ, 0 < t → ∀ q : Fin d → ℝ, MinimaxSLP.ObjSDP.Qval W T h (t • q) x = t * MinimaxSLP.ObjSDP.Qval W T h q x) ∧
∀ a c : Fin d → ℝ, MinimaxSLP.ObjSDP.Qval W T h a x + MinimaxSLP.ObjSDP.Qval W T h c x ≤ MinimaxSLP.ObjSDP.Qval W T h (a + c) x := by sorry
end MinimaxSLP.ObjExtremal
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 586, proof of Theorem 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.