Equation (7.7) — increases along every trajectory
ProvedKellyStochasticNetworks.primal_lyapunov_derivLet be a trajectory of the primal algorithm staying in the positive orthant, so that at time
Then is differentiable with
This is equation (7.7), and it is what makes a Lyapunov function. The derivation is the chain rule: each term of is , and factoring out of the first bracket turns the product into a square. Non-negativity is then immediate, and the derivative vanishes exactly at an equilibrium.
The book is careful about what this does not prove. A strictly increasing Lyapunov function does not by itself give convergence — the derivative could become small fast enough for the trajectory to stall short of the maximum — and closing that gap requires the compactness argument that is the substance of Theorem 7.6.
Formalization Note A trajectory is a differentiable function of real time whose derivative equals the primal drift pointwise; positivity along the trajectory is a hypothesis rather than derived from the dynamics. The conclusion asserts differentiability and the value of the derivative together, and separately its non-negativity.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion
namespace KellyStochasticNetworks
theorem primal_lyapunov_deriv {J R : ℕ} (A : Fin J → Fin R → ℝ) (w κ : Fin R → ℝ)
(p : Fin J → ℝ → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1) (hκ : ∀ r, 0 < κ r)
(hp : ∀ j, Continuous (p j))
(x : ℝ → Fin R → ℝ) (t : ℝ) (hpos : ∀ r, 0 < x t r)
(hode : ∀ r, HasDerivAt (fun s => x s r) (primalDrift A w κ p (x t) r) t) :
HasDerivAt (fun s => primalUtility A w p (x s))
(∑ r, (κ r / x t r)
* (w r - x t r * ∑ j, A j r * p j (linkFlow A (x t) j)) ^ 2) t
∧ 0 ≤ ∑ r, (κ r / x t r)
* (w r - x t r * ∑ j, A j r * p j (linkFlow A (x t) j)) ^ 2 := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.