Proof of Theorem 3.3, p. 590 — 𝕌(𝒬(h, x)) = max over pairs (k, i) of α_k(h − Tx)′p_i + β_k
ProvedMinimaxSLP.RhsExtremal.disutility_Qval_eq_max_pairslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Let , and satisfy complete recourse, (Assumption 2), and dual feasibility, (Assumption 3 at the constant ). Let be the extreme points of (Assumption 5), and let for . Then for every and every ,
and both maxima are attained.
This identity turns the expected disutility into a maximum of finitely many affine functions of , which is what makes the dual (16) and the extremal distribution possible.
Formalization Note Both maxima are stated as IsGreatest of the finite range, which also forces . is the real supremum of over the dual polyhedron.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_MinimaxSLP_RhsExtremal_Model
Formal statement
namespace MinimaxSLP.RhsExtremal
open MeasureTheory Matrix
/-- Proof of Theorem 3.3, p. 590: under complete recourse (Assumption 2), dual feasibility at the
constant `q` (Assumption 3), Assumption 5 (`p_1, …, p_N` are the extreme points of
`{π : W′π ≤ q}`) and `α_k ≥ 0`, for every `h ∈ ℝʳ` the second-stage value is the largest of the
`(h − T x)′p_i`, and `𝕌(𝒬(h, x)) = max_{k, i} (α_k (h − T x)′p_i + β_k)`; both maxima are attained
(`IsGreatest` of the finite range). -/
theorem disutility_Qval_eq_max_pairs {r d n K N : ℕ} [NeZero K]
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (q : Fin d → ℝ)
(α β : Fin K → ℝ) (ps : Fin N → Fin r → ℝ)
(hα : ∀ k, 0 ≤ α k)
(hA2 : ∀ z : Fin r → ℝ, ∃ w : Fin d → ℝ, 0 ≤ w ∧ W *ᵥ w = z)
(hA3 : ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(hA5 : Set.range ps = Set.extremePoints ℝ {π : Fin r → ℝ | Wᵀ *ᵥ π ≤ q})
(x : Fin n → ℝ) (h : Fin r → ℝ) :
IsGreatest (Set.range fun i : Fin N => (h - T *ᵥ x) ⬝ᵥ ps i) (MinimaxSLP.RhsSDP.Qval W T q h x) ∧
IsGreatest (Set.range fun ki : Fin K × Fin N => α ki.1 * ((h - T *ᵥ x) ⬝ᵥ ps ki.2) + β ki.1)
(MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.RhsSDP.Qval W T q h x)) := by sorry
end MinimaxSLP.RhsExtremal
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 590, proof of Theorem 3.3 (first display); with p. 589, proof of Theorem 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.