§2.1, p. 211 — strong duality v(x, Y) = L(x, μ_*), μ_* is a supergradient, and a unique μ_* is the gradient
ProvedRLPBidPrice.Unbiased.strong_duality_subgradientLet be a 0/1 incidence matrix with nonzero columns, , and , with and as above. Then:
- an optimal dual price vector exists: some minimizes over ;
- (strong duality and the supergradient inequality) every such minimizer satisfies and
- if the minimizer is unique and for every , then is differentiable at with gradient .
These are the facts from LP duality that turn the question of differentiability of into the uniqueness of .
Formalization Note. The paper says " is always a subgradient of "; is concave in , so this is meant in the concave sense (a supergradient), stated here as the displayed inequality, over the feasible capacities . The gradient in part 3 is expressed as HasFDerivAt with the linear functional ; it is taken at an interior point . The time index is dropped.
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model open MeasureTheory Matrix
namespace RLPBidPrice.Unbiased
theorem strong_duality_subgradient {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₀) :
(∃ μ, IsDualOpt A r x y₀ μ) ∧
(∀ μ, IsDualOpt A r x y₀ μ →
piValue A r x y₀ = lagr A r x y₀ μ ∧
∀ z : Fin m → ℝ, 0 ≤ z → piValue A r z y₀ ≤ piValue A r x y₀ + μ ⬝ᵥ (z - x)) ∧
(∀ μ, IsDualOpt A r x y₀ μ → (∀ μ', IsDualOpt A r x y₀ μ' → μ' = μ) →
(∀ i, 0 < x i) → HasFDerivAt (fun x' => piValue A r x' y₀) (gradCLM μ) x) := by sorry
end RLPBidPrice.Unbiased
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a real matrix whose entries are all or and whose every column has a nonzero entry. Assume further:
- with ;
- with (zero coordinates allowed);
- with .
Define, for ,
a real supremum, if empty. Define
Call dual-optimal if and for all .
The statement asserts all three of the following:
- Existence. A dual-optimal exists.
- Strong duality and supergradient. Every dual-optimal satisfies . It also satisfies, for every with (and only such ),
- Gradient. Suppose is dual-optimal, every dual-optimal equals , and additionally every . Then , as a function on all of , is Fréchet differentiable at with derivative , i.e. gradient .
Degenerate cases.
- If , the incidence condition forces . All three parts then hold trivially, with .
- If , for and .
- Part 3 applies only when is strictly positive. For with a zero coordinate it asserts nothing.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.