Lemma 2.1, p. 585 — for x ∈ X, : every yields a feasible point of (9) with value
ProvedMinimaxSLP.ObjExtremal.lemma_2_1dualitymoment-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let and assume that , that for every (Assumption 3), that for all , and that is symmetric with (Assumption 4). Then:
- for every the function is -integrable, and there is a feasible point of (9) whose objective value equals the expectation:
- consequently
The feasible point of part 1 consists of the scaled conditional moments of and of a dual-optimal solution of the second-stage problem on the event that the th piece of attains the maximum (ties broken arbitrarily). This upper bound is one half of the identity of Theorem 2.2.
Formalization Note Part 1 is the form in which the paper's proof establishes the lemma; part 2 is the printed statement. Integrability is stated explicitly because the Bochner integral of a non-integrable function is in Lean.
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
/-- Lemma 2.1 (p. 585): for every `x ∈ MinimaxSLP.ObjSDP.X`, `Z_DD(x) ≥ Z(x)`. In the form the proof gives it:
every `P ∈ 𝒫` has an integrable `𝕌(𝒬(·, x))` and a feasible point of (9) (the scaled
conditional moments) whose objective value equals `E_P[𝕌(𝒬(q̃, x))]`; hence `Z(x) ≤ Z_DD(x)`. -/
theorem lemma_2_1 {m₁ n r d K : ℕ} [NeZero K]
(A : Matrix (Fin m₁) (Fin n) ℝ) (b : Fin m₁ → ℝ)
(W : Matrix (Fin r) (Fin d) ℝ) (T : Matrix (Fin r) (Fin n) ℝ) (h : Fin r → ℝ)
(α β : Fin K → ℝ) (hα : ∀ k, 0 ≤ α k)
(μ : Fin d → ℝ) (Q : Matrix (Fin d) (Fin d) ℝ)
(hQ : Q.IsSymm) (hA4 : (Q - Matrix.vecMulVec μ μ).PosDef)
(hA3 : ∀ q : Fin d → ℝ, ∃ π : Fin r → ℝ, Wᵀ *ᵥ π ≤ q)
(x : Fin n → ℝ) (hx : x ∈ MinimaxSLP.ObjSDP.X A b) (hrec : (MinimaxSLP.ObjSDP.recourseSet W T h x).Nonempty) :
(∀ P ∈ MinimaxSLP.ObjSDP.momentClass μ Q,
Integrable (fun q => MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.ObjSDP.Qval W T h q x)) P ∧
∃ s ∈ feasible9 W α μ Q, ∫ q, MinimaxSLP.ObjSDP.disutility α β (MinimaxSLP.ObjSDP.Qval W T h q x) ∂P = obj9 T h β x s) ∧
MinimaxSLP.ObjSDP.Zx W T h α β μ Q x ≤ ZDD W T h α β μ Q 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. 585, Lemma 2.1 and its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.