Theorem 3.10 — a minimizer of the Dual problem satisfies the conditions on
ProvedKellyStochasticNetworks.dual_optimum_conditionsSection 3.4 looks for the mode of the equilibrium distribution (3.3) and, after Stirling's approximation and a continuous relaxation, arrives at the Primal problem (3.4): maximize over subject to . Its Lagrangian dual is the Dual problem (3.5):
Let minimize this objective over the positive orthant. Then for every link ,
Under the substitution these are precisely the conditions on , equation (3.6), of Theorem 3.10, and they have a fluid-flow reading: is the arrival stream on route thinned once for each circuit it requests from each link, so the left-hand side is the aggregate flow on link ; the conditions say that flow never exceeds the link's capacity, and that blocking occurs only on links running at full capacity.
The book obtains them exactly this way — the Dual objective is convex and differentiable and grows to infinity in each coordinate, so its minimum over is attained, and at the minimum the partial derivative in vanishes if and is non-negative if . This is what establishes the existence of a vector satisfying (3.6) without appealing to the strong Lagrangian principle.
Formalization Note Minimality is stated directly as the defining inequality over the positive orthant rather than through an optimization predicate, and the conclusion is the displayed pair of conditions rather than a statement about a derivative, so no differentiability API is presupposed. The incidence matrix has non-negative integer entries, the general case of section 3.3.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Balance import Definitions.Def_KellyStochasticNetworks_Erlang import Definitions.Def_KellyStochasticNetworks_Migration import Definitions.Def_KellyStochasticNetworks_LossNetwork
namespace KellyStochasticNetworks
theorem dual_optimum_conditions {J R : ℕ} (A : Fin J → Fin R → ℕ) (ν : Fin R → ℝ)
(C : Fin J → ℕ) (hν : ∀ r, 0 < ν r) (y : Fin J → ℝ) (hy : ∀ j, 0 ≤ y j)
(hmin : ∀ z : Fin J → ℝ, (∀ j, 0 ≤ z j) → dualObjective A ν C y ≤ dualObjective A ν C z) :
∀ j, (0 < y j →
(∑ r, (A j r : ℝ) * ν r * Real.exp (-∑ i, y i * (A i r : ℝ))) = (C j : ℝ))
∧ (y j = 0 →
(∑ r, (A j r : ℝ) * ν r * Real.exp (-∑ i, y i * (A i r : ℝ))) ≤ (C j : ℝ)) := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.