Lemma 2 — |v(x + h eⁱ, Y) − v(x, Y)| ≤ h r̄ with r̄ = max_j r^j
ProvedRLPBidPrice.Directional.piValue_lipschitzLet be a 0/1 leg–itinerary incidence matrix with nonzero columns, the fares, a capacity vector and a demand vector, and let . For every leg and every ,
where is the -th unit vector.
This is the paper's Lipschitz bound (Lemma 2: " satisfies the Lipschitz condition in Lemma 1"): a constant in each coordinate direction, uniform in . In the nondifferentiable case it is what makes the difference quotients of uniformly bounded.
Formalization Note. is written (⨆ j, r j), which is for and when there are no itineraries. The paper's "for all " is restricted to : for capacities with a negative entry the LP is infeasible and has no value. Fares are an implicit hypothesis (revenues): if every then and the bound fails. The time index is dropped.
import Mathlib import Definitions.Def_RLPBidPrice_Directional_Model open MeasureTheory Matrix
namespace RLPBidPrice.Directional
/-- Lemma 2 (p. 210) and the bound preceding it: raising the capacity of one leg by `h ≥ 0`
changes the perfect-information LP value by at most `h · r̄`, `r̄ = max_j r^j`. -/
theorem piValue_lipschitz {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : Fin n → ℝ)
(hA : IsIncidence A) (hr : 0 ≤ r) (x : Fin m → ℝ) (hx : 0 ≤ x)
(y₀ : Fin n → ℝ) (hy₀ : 0 ≤ y₀) (i : Fin m) (h : ℝ) (hh : 0 ≤ h) :
|piValue A r (x + h • Pi.single i 1) y₀ - piValue A r x y₀| ≤ h * ⨆ j, r j := 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 real matrix, and let . All vector inequalities are componentwise.
Hypotheses.
- is an incidence matrix: every entry is or , and every column has at least one nonzero entry.
- .
- with .
- with .
- is an index.
- with .
Let be the -th standard unit vector of . Define
with the real-number convention that this is when the set is empty or unbounded above.
Conclusion.
where is the supremum over in . For this is .
Degenerate cases.
- Under these hypotheses both LPs are feasible ( works), so neither value is the junk value.
- If , the claim is .
- If : the empty supremum is and both values are , so the claim is .
- If : no index exists, so the statement is vacuous. The incidence hypothesis would also then force .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.