Theorem 2 (primal half) — the SDP (3.14) conservatively approximates 𝒮𝒫^u, and val 𝒮𝒫^u = val (3.14) for l = 1
ProvedPrimalDualLDR.RandomRecourse.theorem_2_primalLet be a probability measure on whose support is the quadratically constrained set
with symmetric , and assume is nonempty, bounded and spans . Consider the one-stage stochastic program with costs , right-hand side and random recourse matrix with rows ; its primal linear decision rule approximation (decisions , slacks ); and the SDP (3.14), both with objective , . Then:
- (3.14) conservatively approximates . Every feasible in (3.14) yields feasible in with the same objective value; hence
- Exactness for one quadratic constraint. If and is strictly feasible, then is equivalent to (3.14):
The result turns the semi-infinite program , an upper bound on the stochastic program , into a semidefinite program of size polynomial in , whose value is an upper bound on in general and equal to it when the support is cut out by a single quadratic inequality (an ellipsoid in the hyperplane ).
Formalization Note This is the primal half of the paper's Theorem 2. The clauses "the SDP (3.18) progressively approximates " and, for , " is equivalent to (3.18)" are false in this preprint (a strictly feasible instance with has ) and are not stated; the claim that the SDP sizes are polynomial and efficiently solvable is informal and omitted. Optimal values are EReal infima ( if infeasible, if unbounded). "Equivalent" is read as equality of optimal values. Strict feasibility of is condition (2.9) of §2 with replaced by ; it is kept in clause 2 as printed.
import Mathlib import Definitions.Def_PrimalDualLDR_RandomRecourse_Problems open MeasureTheory Matrix
namespace PrimalDualLDR.RandomRecourse
/-- **Kuhn, Wiesemann, Georghiou (preprint 2009), Theorem 2, p. 17 — primal half.** If `P` has a
quadratically constrained support `Ξ` of the type (3.11) (nonempty, bounded, spanning `ℝ^k`), then
(a) the SDP (3.14) conservatively approximates `𝒮𝒫^u`: every `(X, S, Λ)` feasible in (3.14)
gives `(X, S)` feasible in `𝒮𝒫^u` with the same objective `Tr(MCᵀX)`, hence
`val 𝒮𝒫^u ≤ val (3.14)`; and
(b) if `l = 1` and `𝒮𝒫` is strictly feasible, then `𝒮𝒫^u` is equivalent to (3.14):
`val 𝒮𝒫^u = val (3.14)`.
The clauses of Theorem 2 about the SDP (3.18) and `𝒮𝒫^l` are not stated (false in this
preprint); "polynomial size / efficiently solvable" is informal and omitted. -/
theorem theorem_2_primal (σ : Setting) (hσ : σ.Standing) :
(∀ (X : Matrix (Fin σ.n) (Fin σ.k) ℝ) (S : Fin σ.m → Matrix (Fin σ.k) (Fin σ.k) ℝ)
(Λ : Matrix (Fin σ.m) (Fin σ.l) ℝ), σ.Feas314 X S Λ → σ.FeasSPu X S) ∧
σ.valSPu ≤ σ.valSDP314 ∧
(σ.l = 1 → σ.StrictlyFeasible → σ.valSPu = σ.valSDP314) := by sorry
end PrimalDualLDR.RandomRecourse
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.