Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.1, p. 212 (corrected: ≤ for ≥, z − x for z − y) — E μ(x, Y) is a supergradient of J^PI at x

Proved
RLPBidPrice.Directional.expected_dual_supergradient

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

convex-analysislinear-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management

Let AAA be a 0/1 incidence matrix with nonzero columns, r≥0r \ge 0r≥0, and xxx a capacity vector with every component xi>0x^i > 0xi>0. Let YYY be a random demand vector on a probability space (Ω,P)(\Omega, P)(Ω,P), measurable and with Y≥0Y \ge 0Y≥0 almost surely, and let μ(ω)\mu(\omega)μ(ω) be a (strongly) measurable random vector that is, for almost every ω\omegaω, an optimal vector of dual prices for (x,Y(ω))(x, Y(\omega))(x,Y(ω)), i.e. minimizes L(x,⋅)L(x, \cdot)L(x,⋅) over μ≥0\mu \ge 0μ≥0. Then for every capacity vector z≥0z \ge 0z≥0,

JPI(z)≤JPI(x)+(E μ)⊤(z−x),JPI(x)=E v(x,Y).J^{PI}(z) \le J^{PI}(x) + \big(\mathbb{E}\,\mu\big)^\top (z - x), \qquad J^{PI}(x) = \mathbb{E}\, v(x, Y).JPI(z)≤JPI(x)+(Eμ)⊤(z−x),JPI(x)=Ev(x,Y).

That is, the expected dual price vector is a supergradient of the concave function JPIJ^{PI}JPI at xxx (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 μ(x,Y)\mu(x, Y)μ(x,Y) 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 Eμ(x,Y)\mathbb{E}\mu(x, Y)Eμ(x,Y) is defined. x>0x > 0x>0 is the paper's implicit setting ("all terms above are uniformly bounded in YYY": with x>0x > 0x>0 every optimal dual price lies in [0,max⁡jrj]m[0, \max_j r^j]^m[0,maxj​rj]m; with a zero capacity the optimal dual prices of that leg are unbounded and Eμ\mathbb{E}\muEμ need not exist). Eμ\mathbb{E}\muEμ is the Bochner integral of the Rm\mathbb{R}^mRm-valued random vector. The time index kkk is dropped.

Correction. The paper prints JkPI(z)≥JkPI(x)+Eμ⊤(x,Y)(z−y)J_k^{PI}(z) \ge J_k^{PI}(x) + E\mu^\top(x, Y)(z - y)JkPI​(z)≥JkPI​(x)+Eμ⊤(x,Y)(z−y): the inequality sign is reversed (concavity; the one-leg example r=1r = 1r=1, Y=5Y = 5Y=5, x=1x = 1x=1, z=10z = 10z=10 gives 5≥105 \ge 105≥10) and "z−yz - yz−y" is a misprint for "z−xz - xz−x".

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Directional_Model

open MeasureTheory Matrix
Formal statement
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
Source
Talluri, van Ryzin, A Randomized Linear Programming Method for Computing Network Bid Prices, Transp. Sci. 33(2), 1999, p. 212, §3.1, second display
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let m,n∈Nm, n \in \mathbb{N}m,n∈N, let Ω\OmegaΩ be a measurable space, and let PPP be a probability measure on Ω\OmegaΩ. Let AAA be a real m×nm \times nm×n matrix and r∈Rnr \in \mathbb{R}^nr∈Rn. All vector inequalities are componentwise.

Hypotheses.

  • AAA is an incidence matrix: every entry is 000 or 111, and every column has at least one nonzero entry.
  • r≥0r \ge 0r≥0.
  • x∈Rmx \in \mathbb{R}^mx∈Rm with xi>0x_i > 0xi​>0 for every iii.
  • Y:Ω→RnY : \Omega \to \mathbb{R}^nY:Ω→Rn is measurable, and Y(ω)≥0Y(\omega) \ge 0Y(ω)≥0 for PPP-almost every ω\omegaω.
  • μ:Ω→Rm\mu : \Omega \to \mathbb{R}^mμ:Ω→Rm is PPP-almost-everywhere strongly measurable.
  • For PPP-almost every ω\omegaω, μ(ω)\mu(\omega)μ(ω) is an optimal dual price at (x,Y(ω))(x, Y(\omega))(x,Y(ω)). That is, μ(ω)≥0\mu(\omega) \ge 0μ(ω)≥0 and μ(ω)\mu(\omega)μ(ω) minimises
μ′↦∑jYj(ω)max⁡(0, rj−∑iμi′Aij)+μ′⋅x\mu' \mapsto \sum_j Y_j(\omega)\max\Big(0,\ r_j - \sum_i \mu'_i A_{ij}\Big) + \mu'\cdot xμ′↦j∑​Yj​(ω)max(0, rj​−i∑​μi′​Aij​)+μ′⋅x

over all μ′≥0\mu' \ge 0μ′≥0.

  • z∈Rmz \in \mathbb{R}^mz∈Rm with z≥0z \ge 0z≥0.

Definitions used.

  • v(x,y0)=sup⁡{ r⋅y:Ay≤x, 0≤y≤y0 }v(x,y_0) = \sup\{\, r\cdot y : Ay \le x,\ 0 \le y \le y_0 \,\}v(x,y0​)=sup{r⋅y:Ay≤x, 0≤y≤y0​}, which is 000 if the set is empty.
  • J(x)=∫Ωv(x,Y(ω)) dP(ω)J(x) = \int_\Omega v(x, Y(\omega))\, dP(\omega)J(x)=∫Ω​v(x,Y(ω))dP(ω), the Bochner integral, which is 000 if the integrand is not integrable.
  • μˉ=∫Ωμ(ω) dP(ω)∈Rm\bar\mu = \int_\Omega \mu(\omega)\, dP(\omega) \in \mathbb{R}^mμˉ​=∫Ω​μ(ω)dP(ω)∈Rm, the Bochner integral, which is the zero vector if μ\muμ is not PPP-integrable.

Conclusion.

J(z)  ≤  J(x)+μˉ⋅(z−x).J(z) \;\le\; J(x) + \bar\mu \cdot (z - x).J(z)≤J(x)+μˉ​⋅(z−x).

What is not assumed. Neither YYY nor μ\muμ is assumed integrable. So J(z)J(z)J(z), J(x)J(x)J(x) and μˉ\bar\muμˉ​ each stand for the true integral only when the relevant function is integrable, and are replaced by 000 otherwise. The conclusion is asserted in all cases, including mixed ones, for example μˉ=0\bar\mu = 0μˉ​=0 because μ\muμ is not integrable while J(x)J(x)J(x) and J(z)J(z)J(z) are genuine integrals. On the null set where Y(ω)≱0Y(\omega) \not\ge 0Y(ω)≥0, the integrand vvv may take its junk value 000.

Degenerate cases.

  • If m=0m = 0m=0: the incidence hypothesis forces n=0n = 0n=0, and the claim is 0≤00 \le 00≤0.
  • If n=0n = 0n=0 and m≥1m \ge 1m≥1: v≡0v \equiv 0v≡0 on z≥0z \ge 0z≥0, so J(z)=J(x)=0J(z) = J(x) = 0J(z)=J(x)=0. Almost every μ(ω)\mu(\omega)μ(ω) must then be 000, because μ(ω)⋅x\mu(\omega)\cdot xμ(ω)⋅x is minimised at 000 with x>0x > 0x>0. The claim is 0≤00 \le 00≤0.
  • The almost-sure optimality hypothesis may be unsatisfiable, in which case the statement is vacuous.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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