Proposition 6 — an S-lemma certificate S − Σ λ_ℓ W_ℓ ⪰ 0 implies ξᵀSξ ≥ 0 P-a.s.; the converse holds for l = 1
ProvedPrimalDualLDR.RandomRecourse.proposition_6p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimizations-lemmasemidefinite-programming
Assume the standing assumptions of §3: with symmetric is the support of the probability measure , and it is nonempty, bounded and spans . Fix a symmetric matrix and consider
- (i) there is with and ;
- (ii) -almost surely.
Then, for every , (i) implies (ii); and if , (ii) implies (i):
Applied to each slack matrix , this replaces the semi-infinite inequality constraints of by linear matrix inequalities; it is why (3.14) is a conservative approximation of in general and an exact one when .
Formalization Note (ii) is stated -almost surely, as printed. is Mathlib's PosSemidef; is componentwise.
Preamble
import Mathlib import Definitions.Def_PrimalDualLDR_RandomRecourse_Setting open MeasureTheory Matrix
Formal statement
namespace PrimalDualLDR.RandomRecourse
/-- **Kuhn, Wiesemann, Georghiou (preprint 2009), Proposition 6, p. 12.** Under the standing
assumptions of §3, for a fixed symmetric `S ∈ 𝕊` consider
(i) `∃ λ ∈ ℝ^l, λ ≥ 0, S − Σ_ℓ λ_ℓ W_ℓ ⪰ 0`; (ii) `ξᵀSξ ≥ 0` `P`-almost surely.
For every `l`, (i) implies (ii); if `l = 1`, (ii) implies (i). -/
theorem proposition_6 (σ : Setting) (hσ : σ.Standing)
(S : Matrix (Fin σ.k) (Fin σ.k) ℝ) (hS : S.IsSymm) :
((∃ lam : Fin σ.l → ℝ, (∀ ℓ, 0 ≤ lam ℓ) ∧ (S - ∑ ℓ : Fin σ.l, lam ℓ • σ.W ℓ).PosSemidef) →
∀ᵐ ξ ∂σ.P, 0 ≤ ξ ⬝ᵥ (S *ᵥ ξ)) ∧
(σ.l = 1 → (∀ᵐ ξ ∂σ.P, 0 ≤ ξ ⬝ᵥ (S *ᵥ ξ)) →
∃ lam : Fin σ.l → ℝ, (∀ ℓ, 0 ≤ lam ℓ) ∧ (S - ∑ ℓ : Fin σ.l, lam ℓ • σ.W ℓ).PosSemidef) := by sorry
end PrimalDualLDR.RandomRecourse
Source
Kuhn, Wiesemann, Georghiou, Primal and dual linear decision rules in stochastic and robust optimization, Optimization Online 2009/02/2218, p. 12, Proposition 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.