Theorem 7.6 (proof) — a stationary point of is an equilibrium of the primal algorithm
ProvedKellyStochasticNetworks.primal_equilibriumcontrol-theoryoptimizationstochastic-networks
For a flow vector in the positive orthant and gains , the following are equivalent:
- is a stationary point of the Lyapunov function, for every route ;
- is an equilibrium of the primal algorithm, for every route .
The two differ by the factor , which is positive, so on the positive orthant they are the same condition. Combined with strict concavity, this is the step of Theorem 7.6 that identifies the maximizer of with the unique rest point of the dynamics — the reason the decentralized algorithm can be said to solve the optimization problem at all, before any question of convergence arises.
Formalization Note Positivity of every and of every gain is what makes the equivalence hold in both directions; without them the second condition is strictly weaker.
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion
Formal statement
namespace KellyStochasticNetworks
theorem primal_equilibrium {J R : ℕ} (A : Fin J → Fin R → ℝ) (w κ : Fin R → ℝ)
(p : Fin J → ℝ → ℝ) (hκ : ∀ r, 0 < κ r) (x : Fin R → ℝ) (hx : ∀ r, 0 < x r) :
(∀ r, w r / x r - ∑ j, A j r * p j (linkFlow A x j) = 0)
↔ ∀ r, primalDrift A w κ p x r = 0 := by sorry
end KellyStochasticNetworksSource
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 164 (PDF p. 172), in the proof of Theorem 7.6: 'setting these derivatives to zero identifies the maximum, x say. The derivative (7.5) is zero at x, and hence x is an equilibrium point.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.