Theorem 2.3 — under complete fixed recourse the expected recourse is finite, convex and Lipschitz
ProvedKallMayerSLP.Recourse.theorem_2_3Throughout, 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 Assumptions 2.1 and 2.2 and that , i.e. is square integrable with respect to . Then the expected recourse
satisfies:
- for every , is finite: is finite for -almost every and integrable;
- is convex on ;
- is Lipschitz continuous: there is with for all .
Hence the two-stage problem (2.3), minimize subject to , , is a convex optimization problem with a Lipschitz continuous objective. This is the basic well-posedness result for two-stage stochastic linear programs with a general (not necessarily discrete) distribution.
Formalization Note is the published KallMayer.Recourse.ExpectedRecourse, the Bochner integral of the real part of the EReal recourse value; clause 1 makes this a genuine finite integral. is the Euclidean norm.
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: 𝒬(x) = ∫_Ξ Q(x; T(ξ), h(ξ), q(ξ)) ℙ_ξ(dξ) finitely valued → Q(x; ξ) finite μ-a.e., its real part integrable (with measurability), and 𝒬 = the published
KallMayer.Recourse.ExpectedRecourse(Bochner integral of the real part); reason: this is what a finite Lebesgue integral of an extended-real function means - encoding: the norm ‖x⁽¹⁾ − x⁽²⁾‖ → the Euclidean norm
‖WithLp.toLp 2 (x₁ - x₂)‖; reason: the book's ‖·‖ on ℝ^{n₁} - generalization: clause a) for x ∈ B₁ = {x | Ax = b, x ≥ 0} → every x ∈ ℝ^{n₁}; reason: Assumption 2.1 makes the second-stage LP feasible for every x (proof of a)); B₁ ⊂ ℝ^{n₁}, so the statement specializes to the book's
- reading: 'Hence, (2.3) is a convex optimization problem with a Lipschitz continuous objective function' → not restated; reason: it follows from a) and b) because the objective is cᵀx + 𝒬(x) and B₁ is convex; it adds no condition on 𝒬
import Mathlib import Definitions.Def_KallMayer_Recourse_CompleteRecourse import Definitions.Def_KallMayer_Recourse_PointwiseRecourse import Definitions.Def_KallMayer_Recourse_ExpectedRecourse import Definitions.Def_KallMayerSLP_Recourse_RandomData open MeasureTheory open KallMayer.Recourse (CompleteRecourse PointwiseRecourse ExpectedRecourse) open Matrix
namespace KallMayerSLP.Recourse
/-- Theorem 2.3 (Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Theorem 2.3, p.208,
PDF 217): since `ξ ∈ L²(Ω, ℝʳ)`, the expected recourse
`𝒬(x) = ∫_Ξ Q(x; T(ξ), h(ξ), q(ξ)) ℙ_ξ(dξ)` is
a) finitely valued `∀ x ∈ B₁`, and
b) a convex and Lipschitz continuous function in `x`.
The standing assumptions of §2.1 are in force: `W` fixed with complete recourse (Assumption 2.1,
(2.6)), `{u | Wᵀu ≤ q(ξ)} ≠ ∅` for every `ξ ∈ Ξ = supp ℙ_ξ` (Assumption 2.2, (2.8)), and the data
affine in `ξ` (2.1).
**Formalization Note.** `μ = ℙ_ξ` on `ℝʳ` (canonical space, `ξ = id`), `Ξ = μ.support`,
`ξ ∈ L²` is `MemLp id 2 μ`. The expected recourse is the published `KallMayer.Recourse.ExpectedRecourse`,
the Bochner integral of the real part of the `EReal` recourse value. Clause a) says that this integral
is a genuine finite integral: the recourse value is finite `μ`-a.e. and its real part is integrable
(including measurability); it is stated for every `x ∈ ℝ^{n₁}`, which contains the book's `x ∈ B₁`.
Clause b) is convexity on `ℝ^{n₁}` and a Lipschitz bound in the Euclidean norm. -/
theorem theorem_2_3 {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₁ → ℝ,
(∀ᵐ ξ ∂μ, PointwiseRecourse W (D.T ξ) (D.h ξ) (D.q ξ) x ≠ ⊥ ∧
PointwiseRecourse W (D.T ξ) (D.h ξ) (D.q ξ) x ≠ ⊤) ∧
Integrable (fun ξ => (PointwiseRecourse W (D.T ξ) (D.h ξ) (D.q ξ) x).toReal) μ) ∧
ConvexOn ℝ Set.univ (ExpectedRecourse μ W D.T D.h D.q) ∧
∃ L : ℝ, ∀ x₁ x₂ : Fin n₁ → ℝ,
|ExpectedRecourse μ W D.T D.h D.q x₁ - ExpectedRecourse μ W D.T D.h D.q x₂| ≤
L * ‖WithLp.toLp 2 (x₁ - x₂)‖ := by sorry
end KallMayerSLP.Recourse
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.