§3.1, p. 212 (corrected: ≤ for ≥) — an optimal dual price vector μ(x, Y) is a supergradient: v(z, Y) ≤ v(x, Y) + μᵀ(z − x) for all z ≥ 0
ProvedRLPBidPrice.Directional.dualOpt_supergradientLet be a 0/1 incidence matrix with nonzero columns, , a capacity vector and a demand vector. Let be an optimal vector of dual prices for the capacity constraints, i.e. minimizes over . Then for every capacity vector ,
where .
In words: for every realization of demand, the dual price vector is a supergradient of the concave function (the paper says "subgradient").
Formalization Note. ranges over the feasible capacities (for other the LP has no value). The time index is dropped.
Correction. The paper prints the inequality as . Since is concave the inequality goes the other way: with one leg, one itinerary, , , (so ) and , the printed inequality reads .
import Mathlib import Definitions.Def_RLPBidPrice_Directional_Model open MeasureTheory Matrix
namespace RLPBidPrice.Directional
/-- §3.1, p. 212 (sign corrected): an optimal dual price vector `μ` of (14) at `x` is a
supergradient of the concave map `z ↦ v(z, y₀)` on the capacities `z ≥ 0`. -/
theorem dualOpt_supergradient {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₀) (μ : Fin m → ℝ) (hμ : IsDualOpt A r x y₀ μ)
(z : Fin m → ℝ) (hz : 0 ≤ z) :
piValue A r z y₀ ≤ piValue A r x y₀ + μ ⬝ᵥ (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 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 optimal dual price at . That is, and for every , where
- with .
As before, , which is if that set is empty.
Conclusion.
Degenerate cases.
- Because , both LPs are feasible ( works), so neither value is the junk value.
- The hypothesis on may be unsatisfiable for some data (for example, if has no minimiser on the orthant). In that case the statement is vacuous for those data.
- If : and , so optimality forces . The claim reduces to .
- If : the incidence hypothesis forces , and the claim is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.