§4.2, (46)–(50) — the Kuhn–Tucker conditions characterize the solutions of (43); interior solutions equalize
ProvedGenCMu.HeavyTraffic.eq_46_50_kuhn_tuckerFix and , put , let each be convex and continuously differentiable on with derivative (right derivative at ), and let with . Then solves (43) if and only if there are and with
If moreover every , then solves (43) if and only if
for some ; (48) and (50) are the constraint .
The optimal split of the total workload equalizes the indices , which is what the generalized rule does dynamically.
Formalization Note The paper states that the Kuhn–Tucker conditions are sufficient; we state both directions (necessity also holds, the constraints being linear). The rates are fixed numbers, the paper's , at a fixed ; is the paper's read as , the coefficient produced by differentiating the objective.
import Mathlib import Definitions.Def_GenCMu_HeavyTraffic_Model import Definitions.Def_GenCMu_HeavyTraffic_Sequence import Definitions.Def_GenCMu_HeavyTraffic_Limits
namespace GenCMu.HeavyTraffic
open Filter Topology Finset
/-- §4.2, (46)–(50) (pp. 821–822): for `C*` convex and `𝒞¹` on `[0, ∞)`, a point `x ∈ Ω` solves (43)
iff it satisfies the Kuhn–Tucker conditions (46)–(48) with `μ_k = λ_k/ρ_k`; for an interior `x`
they reduce to (49)–(50). -/
theorem eq_46_50_kuhn_tucker {d : ℕ} (lam rho : Fin d → ℝ) (Cs : Fin d → ℝ → ℝ)
(hlam : ∀ k, 0 < lam k) (hrho : ∀ k, 0 < rho k)
(hconv : ∀ k, ConvexOn ℝ (Set.Ici 0) (Cs k)) (hC1 : ∀ k, ContDiffOn ℝ 1 (Cs k) (Set.Ici 0))
(y : ℝ) (x : Fin d → ℝ) (hx : ∀ k, 0 ≤ x k) (hsum : ∑ k, x k = y) :
(IsMin43 lam rho Cs y x ↔
∃ α₀ : ℝ, ∃ α : Fin d → ℝ, (∀ k, 0 ≤ α k) ∧
(∀ k, lam k / rho k * mc Cs k (x k / rho k) - α k = α₀) ∧ (∀ k, α k * x k = 0)) ∧
((∀ k, 0 < x k) →
(IsMin43 lam rho Cs y x ↔ ∃ α₀ : ℝ, ∀ k, lam k / rho k * mc Cs k (x k / rho k) = α₀)) := by sorry
end GenCMu.HeavyTraffic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.