Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Proposition 2, p. 212 — D(x, Y; d) = lim_{h↓0} (1/h)[v(x + hd, Y) − v(x, Y)] = inf{dᵀμ : μ ∈ ∂v(x, Y)}

Proved
RLPBidPrice.Directional.piValue_directional_derivative

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

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

Let AAA be a 0/1 incidence matrix with nonzero columns, r≥0r \ge 0r≥0, xxx a capacity vector with every component xi>0x^i > 0xi>0, and Y≥0Y \ge 0Y≥0 a demand vector. For every direction d∈Rmd \in \mathbb{R}^md∈Rm the one-sided directional derivative of z↦v(z,Y)z \mapsto v(z, Y)z↦v(z,Y) at xxx exists and equals the least value of d⊤μd^\top \mud⊤μ over the superdifferential:

D(x,Y;d)=lim⁡h↓01h[v(x+hd,Y)−v(x,Y)]=inf⁡{d⊤μ:μ∈∂v(x,Y)},D(x, Y; d) = \lim_{h \downarrow 0} \frac{1}{h}\big[v(x + hd, Y) - v(x, Y)\big] = \inf\{d^\top \mu : \mu \in \partial v(x, Y)\},D(x,Y;d)=h↓0lim​h1​[v(x+hd,Y)−v(x,Y)]=inf{d⊤μ:μ∈∂v(x,Y)},

where ∂v(x,Y)={μ:v(z,Y)≤v(x,Y)+μ⊤(z−x) for all z≥0}\partial v(x, Y) = \{\mu : v(z, Y) \le v(x, Y) + \mu^\top (z - x) \text{ for all } z \ge 0\}∂v(x,Y)={μ:v(z,Y)≤v(x,Y)+μ⊤(z−x) for all z≥0}.

The paper cites this as a known fact about concave functions (Bazaraa, Sherali and Shetty 1993, p. 218) and applies it to the LP value in each demand scenario.

Formalization Note. The limit is one-sided, h→0+h \to 0^+h→0+ (nhdsWithin 0 (Set.Ioi 0)): the two-sided limit written in the paper as lim⁡h→0\lim_{h \to 0}limh→0​ does not exist in the nondifferentiable case this section treats (one leg, one itinerary, r=1r = 1r=1, x=1x = 1x=1, Y=1Y = 1Y=1, d=1d = 1d=1: the right quotient is 000, the left one is 111). For small h>0h > 0h>0, x+hd≥0x + hd \ge 0x+hd≥0 because x>0x > 0x>0. The infimum is a real sInf; for x>0x > 0x>0 the superdifferential is nonempty and bounded, so it is an attained minimum. The time index kkk is dropped.

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Directional_Model

open MeasureTheory Matrix
Formal statement
namespace RLPBidPrice.Directional

/-- Proof of Proposition 2, p. 212 (Bazaraa–Sherali–Shetty): at `x > 0` the one-sided
directional derivative of `z ↦ v(z, y₀)` in the direction `d` exists and equals
`inf { dᵀμ : μ ∈ ∂v(x, y₀) }`. -/
theorem piValue_directional_derivative {m n : ℕ} (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 → ℝ) (hy₀ : 0 ≤ y₀) (d : Fin m → ℝ) :
    Filter.Tendsto (fun h : ℝ => h⁻¹ * (piValue A r (x + h • d) y₀ - piValue A r x y₀))
      (nhdsWithin 0 (Set.Ioi 0))
      (nhds (sInf ((fun μ : Fin m → ℝ => d ⬝ᵥ μ) '' superdiff A r x y₀))) := 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, proof of Proposition 2, display (citing Bazaraa, Sherali, Shetty 1993, p. 218)
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 AAA be a real m×nm \times nm×n matrix, and let 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.
  • y0∈Rny_0 \in \mathbb{R}^ny0​∈Rn with y0≥0y_0 \ge 0y0​≥0.
  • d∈Rmd \in \mathbb{R}^md∈Rm is any direction, with no sign or size restriction.

Definitions used.

  • v(z,y0)=sup⁡{ r⋅y:Ay≤z, 0≤y≤y0 }v(z,y_0) = \sup\{\, r\cdot y : Ay \le z,\ 0 \le y \le y_0 \,\}v(z,y0​)=sup{r⋅y:Ay≤z, 0≤y≤y0​}, which is 000 if the set is empty.
  • ∂v(x,y0)\partial v(x,y_0)∂v(x,y0​) is the set of all μ∈Rm\mu \in \mathbb{R}^mμ∈Rm with v(z,y0)≤v(x,y0)+μ⋅(z−x)v(z,y_0) \le v(x,y_0) + \mu\cdot(z-x)v(z,y0​)≤v(x,y0​)+μ⋅(z−x) for every z≥0z \ge 0z≥0.

Conclusion.

lim⁡h→0+v(x+hd, y0)−v(x,y0)h  =  inf⁡{ d⋅μ:μ∈∂v(x,y0) }.\lim_{h \to 0^+} \frac{v(x + h d,\ y_0) - v(x, y_0)}{h} \;=\; \inf\{\, d\cdot\mu : \mu \in \partial v(x,y_0) \,\}.h→0+lim​hv(x+hd, y0​)−v(x,y0​)​=inf{d⋅μ:μ∈∂v(x,y0​)}.

The limit is taken as hhh tends to 000 through strictly positive reals, and it is asserted to exist and to be a finite real number. The right-hand side is the real infimum, which by convention is 000 if ∂v(x,y0)\partial v(x,y_0)∂v(x,y0​) is empty or if d⋅μd\cdot\mud⋅μ is unbounded below on it. So in those cases the statement asserts that the one-sided difference quotient tends to 000.

Degenerate cases.

  • Because x>0x > 0x>0, the point x+hdx + hdx+hd stays ≥0\ge 0≥0 for all small h>0h > 0h>0, so the junk value of vvv at infeasible capacities does not enter the limit.
  • If d=0d = 0d=0: the quotient is identically 000. The claim then says the infimum of {0}\{0\}{0} (or of the empty set) is 000, which holds in both cases.
  • If m=0m = 0m=0: the incidence hypothesis forces n=0n = 0n=0, and everything is 000.
  • If n=0n = 0n=0 and m≥1m \ge 1m≥1: v≡0v \equiv 0v≡0 near xxx, so the claim is lim⁡=0\lim = 0lim=0 and the infimum must be 000.
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