Proof of Theorem 3.2, p. 589 — 𝒬(h, x) = max over the dual extreme points of (h − Tx)′p_i
ProvedMinimaxSLP.RhsSDP.Qval_eq_max_extreme_pointslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Let , and satisfy complete recourse, (Assumption 2), and (Assumption 3 at the constant ), and let be exactly the extreme points of (Assumption 5). Then for every and every ,
and the maximum is attained; in particular .
This replaces the second-stage linear program by a maximum of finitely many affine functions of , which turns each dual constraint into finitely many quadratic inequalities.
Formalization Note The conclusion is IsGreatest of the finite set at , the real supremum over the dual polyhedron; this also forces the list of extreme points to be nonempty, so is a consequence, not a hypothesis.
Preamble
import Mathlib import Definitions.Def_MomentDRO_Conf_Setting import Definitions.Def_WorstCaseVaR_KnownMoments_Basic import Definitions.Def_MinimaxSLP_RhsSDP_Model
Formal statement
namespace MinimaxSLP.RhsSDP
open MeasureTheory Matrix
/-- Proof of Theorem 3.2, p. 589: under complete recourse (Assumption 2), dual feasibility at
the constant `q` (Assumption 3) and Assumption 5 (`p_1, …, p_N`, here `ps`, are exactly the
extreme points of `{π : W′π ≤ q}`), for every `x ∈ ℝⁿ` and `h ∈ ℝʳ` the second-stage value is
the largest of the `(h − T x)′p_i`: `𝒬(h, x) = max_{i} (h − T x)′p_i`, the maximum being
attained (`IsGreatest` of the finite range, which in particular forces `N ≥ 1`). -/
theorem Qval_eq_max_extreme_points {r d n N : ℕ}
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (q : Fin d → ℝ)
(ps : Fin N → Fin r → ℝ)
(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) (Qval W T q h x) := by sorry
end MinimaxSLP.RhsSDP
Source
Bertsimas, Doan, Natarajan & Teo, Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion, Math. Oper. Res. 35(3), 2010, p. 589, proof of Theorem 3.2 (first display); Assumption 5, p. 589
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.