§2.1, p. 583 — strong duality between the moment problem (5) and its dual (6)
ProvedMinimaxSLP.ObjExtremal.strong_dualitydualitymoment-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-duality
Let , assume , Assumption 3 ( for all ), for all , and Assumption 4: is symmetric and the covariance matrix is positive definite. Then the moment problem
and its dual (6),
have the same finite optimal value:
- the set of values , , is nonempty and bounded above, with supremum ;
- the set of objective values of feasible points of (6) is nonempty and bounded below, with infimum ;
- .
The paper obtains this from the strong duality theory of the moment problem (Isii), the interior condition being Assumption 4. It is the step in the final chain of the proof of Theorem 2.2.
Formalization Note The interior condition "the moment vector lies in the interior of the set of feasible moment vectors" is read as Assumption 4. The printed min of (6) is read as an infimum; attainment is not claimed. The same statement appears in the companion mission on Theorem 2.1.
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
/-- §2.1 (p. 583): strong duality `Z(x) = Z_D(x)` between the moment problem (5) and its dual
(6), under Assumption 4 (`Q − μμ′ ≻ 0`, the interior condition). Both optimal values are genuine:
the primal values are bounded above with least upper bound `Z(x)`, the dual values bounded below
with greatest lower bound `Z_D(x)`. -/
theorem strong_duality {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) :
IsLUB (MinimaxSLP.ObjSDP.primalValues W T h α β μ Q x) (MinimaxSLP.ObjSDP.Zx W T h α β μ Q x) ∧
IsGLB (MinimaxSLP.ObjSDP.dualValues6 W T h α β μ Q x) (MinimaxSLP.ObjSDP.ZD W T h α β μ Q x) ∧
MinimaxSLP.ObjSDP.Zx W T h α β μ Q x = MinimaxSLP.ObjSDP.ZD 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. 583, §2.1 (strong duality, citing Isii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.