§3.1, p. 212 (corrected: ≤ for ≥, z − x for z − y) — E μ(x, Y) is a supergradient of J^PI at x
ProvedRLPBidPrice.Directional.expected_dual_supergradientLet be a 0/1 incidence matrix with nonzero columns, , and a capacity vector with every component . Let be a random demand vector on a probability space , measurable and with almost surely, and let be a (strongly) measurable random vector that is, for almost every , an optimal vector of dual prices for , i.e. minimizes over . Then for every capacity vector ,
That is, the expected dual price vector is a supergradient of the concave function at (the paper says "subgradient"). This is the fact behind the RLP estimator in the nondifferentiable case: averaged dual prices estimate a supergradient, not necessarily a gradient.
Formalization Note. The paper's is "the dual solution returned by a given linear programming algorithm"; here it is any measurable selection of optimal dual prices, which is the reading under which is defined. is the paper's implicit setting ("all terms above are uniformly bounded in ": with every optimal dual price lies in ; with a zero capacity the optimal dual prices of that leg are unbounded and need not exist). is the Bochner integral of the -valued random vector. The time index is dropped.
Correction. The paper prints : the inequality sign is reversed (concavity; the one-leg example , , , gives ) and "" is a misprint for "".
import Mathlib import Definitions.Def_RLPBidPrice_Directional_Model open MeasureTheory Matrix
namespace RLPBidPrice.Directional
/-- §3.1, p. 212 (sign corrected): for a measurable selection `μ(ω)` of optimal dual prices
at `x > 0`, the expected dual price `E μ` is a supergradient of `J^PI` at `x`. -/
theorem expected_dual_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 ω)
(μ : Ω → Fin m → ℝ) (hμm : AEStronglyMeasurable μ P)
(hμ : ∀ᵐ ω ∂P, IsDualOpt A r x (Y ω) (μ ω))
(z : Fin m → ℝ) (hz : 0 ≤ z) :
JPI P A r Y z ≤ JPI P A r Y x + (∫ ω, μ ω ∂P) ⬝ᵥ (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 -almost-everywhere strongly measurable.
- For -almost every , is an optimal dual price at . That is, and minimises
over all .
- with .
Definitions used.
- , which is if the set is empty.
- , the Bochner integral, which is if the integrand is not integrable.
- , the Bochner integral, which is the zero vector if is not -integrable.
Conclusion.
What is not assumed. Neither nor is assumed integrable. So , and each stand for the true integral only when the relevant function is integrable, and are replaced by otherwise. The conclusion is asserted in all cases, including mixed ones, for example because is not integrable while and are genuine integrals. On the null set where , the integrand may take its junk value .
Degenerate cases.
- If : the incidence hypothesis forces , and the claim is .
- If and : on , so . Almost every must then be , because is minimised at with . The claim is .
- The almost-sure optimality hypothesis may be unsatisfiable, in which case the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.