Lemma 2.2 — an optimal recourse in exists
ProvedKallMayerSLP.Recourse.lemma_2_2Throughout, is a random vector in with distribution and support (the smallest closed set of probability one); the second-stage data are affine in as in (2.1), and the recourse matrix is fixed. The recourse function is the optimal value of the second-stage LP (2.9),
with value when the LP is infeasible and when it is unbounded. Assumption 2.1 (complete fixed recourse, (2.6)): . Assumption 2.2 ((2.8)): for every .
Assume in addition the standing assumption (p.199) and let be the space of second-stage decisions. Under Assumptions 2.1 and 2.2, for every first-stage decision there is an optimal recourse :
The content is the measurability and square integrability of an optimal selection, which is what makes the two-stage problem (2.3) with equivalent to minimizing plus the expected recourse.
Formalization Note The probability space is the canonical one: , the identity and the Borel sets, so is the set of with MemLp y 2 μ, .
Differences from the source:
- encoding: probability space (Ω, ℱ, P) with ℱ = σ(ξ) and the induced distribution ℙ_ξ on ℝʳ → a probability measure μ = ℙ_ξ on
Fin r → ℝ(canonical space, ξ = id); reason: the statement involves ξ only through ℙ_ξ; same instances - encoding: Ξ = supp ℙ_ξ, the smallest closed set with ℙ_ξ(Ξ) = 1 →
μ.support(Mathlib's support: points all of whose neighbourhoods have positive measure); reason: the two sets coincide in ℝʳ - encoding: T(ξ), h(ξ), q(ξ) affine in ξ by (2.1), W(ξ) ≡ W fixed →
RandomDatawith fields T0, Tj, h0, hj, q0, qj and one fixed matrix W; reason: notation only - encoding: recourse value Q(x; T(ξ), h(ξ), q(ξ)) as an inf with values ±∞ → the published
KallMayer.Recourse.PointwiseRecourse, anERealinfimum (+∞ if infeasible, −∞ if unbounded); reason: the book's convention of p.200; same values - encoding: Y = L²(Ω, ℝ^{n₂}) with ℱ = σ(ξ) → y : ℝʳ → ℝ^{n₂} with
MemLp y 2 μ; reason: σ(ξ)-measurable maps are functions of ξ (Doob–Dynkin); same objects - reading: 'optimal recourse y(·) ∈ Y such that Q(x; T(ξ), h(ξ), q(ξ)) = qᵀ(ξ)y(ξ)' (no quantifier on ξ) → y(ξ) feasible for (2.9) and attaining Q, for every ξ ∈ Ξ; reason: the proof constructs y on the partition of Ξ; the pointwise reading is the stronger one
import Mathlib import Definitions.Def_KallMayer_Recourse_CompleteRecourse import Definitions.Def_KallMayer_Recourse_PointwiseRecourse import Definitions.Def_KallMayerSLP_Recourse_RandomData open MeasureTheory open KallMayer.Recourse (CompleteRecourse PointwiseRecourse) open Matrix
namespace KallMayerSLP.Recourse
/-- Lemma 2.2 (Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Lemma 2.2, p.204,
PDF 213): given Assumptions 2.1 and 2.2, for any `x ∈ ℝ^{n₁}` there exists an optimal recourse
`y(·) ∈ Y = L²(Ω, ℝ^{n₂})` such that `Q(x; T(ξ), h(ξ), q(ξ)) = qᵀ(ξ) y(ξ)`.
Setting (pp.198–203): `μ = ℙ_ξ` is the distribution of `ξ` on `ℝʳ`, `ξ ∈ L²` (p.199), the data are
affine in `ξ` (2.1), the recourse matrix `W` is fixed, Assumption 2.1 is complete recourse (2.6), and
Assumption 2.2 is `{u | Wᵀ u ≤ q(ξ)} ≠ ∅` for all `ξ ∈ Ξ = supp ℙ_ξ` (2.8).
**Formalization Note.** The probability space is the canonical one, `Ω = ℝʳ` with `ξ = id` and
`ℱ = σ(ξ)` = Borel sets, so `Y = L²(Ω, ℝ^{n₂})` is `MemLp y 2 μ` for `y : ℝʳ → ℝ^{n₂}`. "Optimal
recourse" is read pointwise on the support: `y(ξ)` is feasible for (2.9) and attains its value, for
every `ξ ∈ Ξ` (this is what the proof constructs). The recourse function is the published
`KallMayer.Recourse.PointwiseRecourse`, an `EReal` infimum. -/
theorem lemma_2_2 {m₂ n₁ n₂ r : ℕ} (W : Matrix (Fin m₂) (Fin n₂) ℝ) (D : RandomData m₂ n₁ n₂ r)
(μ : Measure (Fin r → ℝ)) [IsProbabilityMeasure μ] (hξ : MemLp id 2 μ)
(hW : CompleteRecourse W)
(hdual : ∀ ξ ∈ μ.support, ∃ u : Fin m₂ → ℝ, W.transpose *ᵥ u ≤ D.q ξ)
(x : Fin n₁ → ℝ) :
∃ y : (Fin r → ℝ) → (Fin n₂ → ℝ), MemLp y 2 μ ∧
∀ ξ ∈ μ.support, W *ᵥ y ξ = D.h ξ - D.T ξ *ᵥ x ∧ 0 ≤ y ξ ∧
PointwiseRecourse W (D.T ξ) (D.h ξ) (D.q ξ) x = ((D.q ξ ⬝ᵥ y ξ : ℝ) : EReal) := by sorry
end KallMayerSLP.Recourse
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.