Proof of Theorem 1, p. 36 — weak duality for the inner LP (C-17) against the dual (4b), (4d)
ProvedDDMomentDRO.Type1.weak_duality_C17distributionally-robustlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-duality
Fix a stage of the Bellman equation (2) under the Type 1 ambiguity set of (3) (with , as in (C-17f)), and a state . Let , and let , be nonnegative with
Then
This is the weak half of the LP duality between the inner maximization (C-17) of (2) and the dual whose constraints are (4b), (4d): every dual feasible point bounds the worst-case expectation from above.
Formalization Note The stage set and the binary-state hypothesis are carried as standing binders of the mission; the statement does not depend on them.
Preamble
import Mathlib import Definitions.Def_DDMomentDRO_Type1_Setting
Formal statement
namespace DDMomentDRO.Type1
open Matrix
/-- Weak duality for the inner LP (C-17) of the Bellman equation (2) under the Type 1 set (3):
for a state `x`, every `p` in the ambiguity set and every dual point `(α, β, γ̲, γ̄)` satisfying
(4b), (4d) at `x`, `∑ₖ pₖ Q_{t+1}(x, ξᵏ) ≤ −αᵀl(x) + βᵀu(x) − γ̲ᵀp̲(x) + γ̄ᵀp̄(x)`. -/
theorem weak_duality_C17 {I J K m : ℕ}
(S : Set ((Fin I → ℝ) × (Fin I → Fin J → ℝ)))
(hbin : ∀ p ∈ S, ∀ i, p.1 i = 0 ∨ p.1 i = 1)
(Qn : (Fin I → ℝ) → Fin K → ℝ) (ξ : Fin K → Fin J → ℝ) (e : Fin m → Fin J → ℕ)
(l u : (Fin I → ℝ) → Fin m → ℝ) (pl pu : (Fin I → ℝ) → Fin K → ℝ)
(x : Fin I → ℝ) (p : Fin K → ℝ) (hp : p ∈ amb1 ξ e l u pl pu x)
(α β : Fin m → ℝ) (γl γu : Fin K → ℝ) (hdual : DualFeas1 Qn ξ e x α β γl γu) :
∑ k, p k * Qn x k ≤ -(α ⬝ᵥ l x) + β ⬝ᵥ u x - γl ⬝ᵥ pl x + γu ⬝ᵥ pu x := by sorry
end DDMomentDRO.Type1
Source
Yu & Shen, Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets, arXiv:2002.12518v3, p. 36, proof of Theorem 1, (C-17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.