Proposition 1, p. 212 (formalized as: a fixed measurable dual selection) — (1/N) Σ μ(x, Yᵢ) converges a.s. to a supergradient of E v(x, Y)
ProvedRLPBidPrice.Directional.averaged_duals_supergradientLet be a 0/1 incidence matrix with nonzero columns, , and a capacity vector with every component . Let be a measurable random demand vector on a probability space with almost surely, and let be measurable random vectors, pairwise independent and each distributed as . Model a linear programming algorithm that is "initialized with the same data on each run" as a measurable map returning, for every demand vector , an optimal vector of dual prices for (a minimizer of over ); write . Then there is a vector such that almost surely
and is a supergradient of at :
The point of the proposition is the contrast with warm-started algorithms, whose returned duals depend on the history and whose averages need not converge.
Formalization Note. "Initialized with the same data on each run (e.g., it is not warm started with data from prior solutions)" is modelled by a fixed function of the current demand vector; its measurability is an added hypothesis (the paper does not discuss it; a measurable selection of optimal duals exists). "Always exists" is read as almost sure convergence, the strong-law sense in which it holds; the limit is deterministic. The samples are the paper's " independent samples of the demand vector" (p. 209); only pairwise independence is assumed. "Subgradient of " is the supergradient inequality on the feasible capacities ( is concave). The time index is dropped.
import Mathlib import Definitions.Def_RLPBidPrice_Directional_Model open MeasureTheory Matrix
namespace RLPBidPrice.Directional
/-- Proposition 1, p. 212, formalized as: if the LP algorithm returns the same dual solution
`f y` whenever it is run on the demand `y` (a fixed measurable function of the data), then for
i.i.d. demand samples the running average of the returned dual prices converges almost surely
to a deterministic vector `g`, and `g` is a supergradient of `J^PI` at `x`. -/
theorem averaged_duals_supergradient {m n : ℕ} {Ω : Type*} [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P]
(A : Matrix (Fin m) (Fin n) ℝ) (r : Fin n → ℝ) (hA : IsIncidence A) (hr : 0 ≤ r)
(x : Fin m → ℝ) (hx : ∀ i, 0 < x i)
(Y : Ω → Fin n → ℝ) (hYm : Measurable Y) (hY : ∀ᵐ ω ∂P, 0 ≤ Y ω)
(f : (Fin n → ℝ) → (Fin m → ℝ)) (hfm : Measurable f)
(hf : ∀ y : Fin n → ℝ, 0 ≤ y → IsDualOpt A r x y (f y))
(Ys : ℕ → Ω → Fin n → ℝ) (hYsm : ∀ k, Measurable (Ys k))
(hind : Pairwise fun k l => ProbabilityTheory.IndepFun (Ys k) (Ys l) P)
(hident : ∀ k, ProbabilityTheory.IdentDistrib (Ys k) Y P P) :
∃ g : Fin m → ℝ,
(∀ᵐ ω ∂P, Filter.Tendsto
(fun N : ℕ => (N : ℝ)⁻¹ • ∑ k ∈ Finset.range N, f (Ys k ω))
Filter.atTop (nhds g)) ∧
∀ z : Fin m → ℝ, 0 ≤ z → JPI P A r Y z ≤ JPI P A r Y x + g ⬝ᵥ (z - x) := by sorry
end RLPBidPrice.Directional
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let , let be a measurable space, and let be a probability measure on . Let be a real matrix and . All vector inequalities are componentwise.
Hypotheses.
- is an incidence matrix: every entry is or , and every column has at least one nonzero entry.
- .
- with for every .
- is measurable, and for -almost every .
- is a single measurable function such that, for every , is an optimal dual price at . That is, and minimises
over . Nothing is required of when .
- are measurable and pairwise independent under . Mutual independence is not required.
- Each has the same distribution under as .
Definitions used.
- , which is if the set is empty.
- , the Bochner integral, which is if the integrand is not integrable.
Conclusion. There exists a vector such that both of the following hold:
- For -almost every ,
At the prefactor is taken as . This term does not affect the limit. 2. For every with ,
The statement does not say how relates to or beyond these two properties. In particular, it does not identify with any expectation. No integrability of is assumed, so and are the true integrals only when those integrands are integrable, and otherwise.
Degenerate cases.
- If : the incidence hypothesis forces . Then is the unique element of and both claims are trivial.
- If and : optimality forces , so the averages are . Then works, since on .
- The hypothesis on may be unsatisfiable for some data (for example, if some has no minimiser, or no measurable choice exists). In that case the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.