Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.2, p. 12 — the μth equality constraint of 𝒮𝒫^u holds P-a.s. iff H_μ = 0 (Ξ with relative interior)

Proved
PrimalDualLDR.RandomRecourse.claim_3_13

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-decision-rulesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimizationstochastic-programming

Assume the standing assumptions of §3: Ξ={ξ: e1⊤ξ=1, ξ⊤Wℓξ≥0, ℓ=1,…,l}\Xi=\{\xi:\ e_1^\top\xi=1,\ \xi^\top W_\ell\xi\ge0,\ \ell=1,\dots,l\}Ξ={ξ: e1⊤​ξ=1, ξ⊤Wℓ​ξ≥0, ℓ=1,…,l} is the support of the probability measure P\mathbb PP, it is nonempty and bounded, it spans Rk\mathbb R^kRk, and every WℓW_\ellWℓ​ is symmetric. Assume in addition that Ξ\XiΞ has a relative interior point: some ξ0∈Ξ\xi_0\in\Xiξ0​∈Ξ and r>0r>0r>0 satisfy ξ∈Ξ\xi\in\Xiξ∈Ξ whenever e1⊤ξ=1e_1^\top\xi=1e1⊤​ξ=1 and ∥ξ−ξ0∥<r\|\xi-\xi_0\|<r∥ξ−ξ0​∥<r.

Let X∈Rn×kX\in\mathbb R^{n\times k}X∈Rn×k, let SμS_\muSμ​ be a symmetric k×kk\times kk×k matrix and μ∈{1,…,m}\mu\in\{1,\dots,m\}μ∈{1,…,m}, and set

Hμ=12(AμX+X⊤Aμ⊤−e1bμ⊤−bμe1⊤)+Sμ.H_\mu=\tfrac12\big(A_\mu X+X^\top A_\mu^\top-e_1b_\mu^\top-b_\mu e_1^\top\big)+S_\mu .Hμ​=21​(Aμ​X+X⊤Aμ⊤​−e1​bμ⊤​−bμ​e1⊤​)+Sμ​.

Then

ξ⊤AμXξ+ξ⊤Sμξ=bμ⊤ξP-a.s.⟺Hμ=0.\xi^\top A_\mu X\xi+\xi^\top S_\mu\xi=b_\mu^\top\xi\quad\mathbb P\text{-a.s.}\qquad\Longleftrightarrow\qquad H_\mu=0 .ξ⊤Aμ​Xξ+ξ⊤Sμ​ξ=bμ⊤​ξP-a.s.⟺Hμ​=0.

This turns each semi-infinite equality constraint of SPu\mathcal{SP}^uSPu into a finite linear matrix equation, which is the equality constraint of the SDP (3.14).

Formalization Note The relative-interior hypothesis is a repair. The paper deduces "the interior of cone(Ξ)\mathrm{cone}(\Xi)cone(Ξ) is nonempty" from "Ξ\XiΞ spans Rk\mathbb R^kRk", which needs Ξ\XiΞ to have dimension k−1k-1k−1; for a nonconvex Ξ\XiΞ of type (3.11) with l≥2l\ge2l≥2 this fails (e.g. k=2k=2k=2 and Ξ={(1,a),(1,b)}\Xi=\{(1,a),(1,b)\}Ξ={(1,a),(1,b)} cut out by (u−a)(u−b)≥0(u-a)(u-b)\ge0(u−a)(u−b)≥0 and −(u−a)(u−b)≥0-(u-a)(u-b)\ge0−(u−a)(u−b)≥0, where H=(ab−(a+b)/2−(a+b)/21)≠0H=\begin{pmatrix}ab&-(a+b)/2\\-(a+b)/2&1\end{pmatrix}\ne0H=(ab−(a+b)/2​−(a+b)/21​)=0 vanishes on Ξ\XiΞ). The paper states on p. 10 that spanning is equivalent to "dimension k−1k-1k−1", and the added hypothesis is that reading. For l=1l=1l=1 it follows from the standing assumptions. SμS_\muSμ​ is assumed symmetric, as in SPu\mathcal{SP}^uSPu; without symmetry only the symmetric part of HμH_\muHμ​ would be determined.

Preamble
import Mathlib
import Definitions.Def_PrimalDualLDR_RandomRecourse_Problems

open MeasureTheory Matrix
Formal statement
namespace PrimalDualLDR.RandomRecourse

/-- **Kuhn, Wiesemann, Georghiou (preprint 2009), §3.2, p. 12 (unnumbered, around (3.13)).**
Under the standing assumptions of §3, for a decision `X ∈ ℝ^{n×k}`, a symmetric slack matrix
`S_μ ∈ 𝕊` and a row `μ`, the `μ`th equality constraint of `𝒮𝒫^u`,
`ξᵀA_μXξ + ξᵀS_μξ = b_μᵀξ` `P`-almost surely, holds if and only if
`H_μ = ½(A_μX + XᵀA_μᵀ − e_1b_μᵀ − b_μe_1ᵀ) + S_μ = 0`.

Repair: the hypothesis `hrelint` (some point of `Ξ` has a neighbourhood, relative to the
hyperplane `{e_1ᵀξ = 1}`, contained in `Ξ`) is added. The paper derives "the interior of
`cone(Ξ)` is nonempty" from "`Ξ` spans `ℝ^k`", which fails when `Ξ` is not convex (for `l ≥ 2`,
`Ξ` can be two points); `hrelint` is the paper's "`Ξ` has dimension `k − 1`" (p. 10). For
`l = 1` it follows from the standing assumptions. -/
theorem claim_3_13 (σ : Setting) (hσ : σ.Standing)
    (hrelint : ∃ ξ₀ ∈ σ.Xi, ∃ r : ℝ, 0 < r ∧
      ∀ ξ : Fin σ.k → ℝ, σ.e1 ⬝ᵥ ξ = 1 → dist ξ ξ₀ < r → ξ ∈ σ.Xi)
    (X : Matrix (Fin σ.n) (Fin σ.k) ℝ) (Sμ : Matrix (Fin σ.k) (Fin σ.k) ℝ) (hS : Sμ.IsSymm)
    (μ : Fin σ.m) :
    (∀ᵐ ξ ∂σ.P, ξ ⬝ᵥ ((σ.A μ * X) *ᵥ ξ) + ξ ⬝ᵥ (Sμ *ᵥ ξ) = σ.B μ ⬝ᵥ ξ) ↔
      σ.H X Sμ μ = 0 := 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, §3.2, (3.13) and the paragraph after it
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me