Equation (2.2): the Lagrangian maximum and dual value
ProvedKellyLossNetworks.Primal.lagrangian_maxconvex-dualityloss-networksoperations-researchp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For offered traffic and any nonnegative multiplier vector , let be the Lagrangian of the primal problem with nonnegative route flow and slack . Its maximum is attained at and , with value
This identifies the published dual objective as the Lagrangian maximum.
Preamble
import Mathlib import Definitions.Def_KellyLossNetworks_Primal_Problem
Formal statement
namespace KellyLossNetworks.Primal
/-- Kelly, *Loss networks* (1991), §2.1, pp. 327–328, Lagrangian and (2.2)–(2.3).
Formalization Note: `z = 0` is a maximizing slack vector when `y ≥ 0`. -/
theorem lagrangian_max {J R : ℕ} (A : Fin J → Fin R → ℕ)
(ν : Fin R → ℝ) (C : Fin J → ℕ) (hν : ∀ r, 0 < ν r)
(y : Fin J → ℝ) (hy : ∀ j, 0 ≤ y j) :
(∀ (x : Fin R → ℝ) (z : Fin J → ℝ),
(∀ r, 0 ≤ x r) → (∀ j, 0 ≤ z j) →
lagrangian A ν C x z y ≤ KellyStochasticNetworks.dualObjective A ν C y) ∧
lagrangian A ν C (primalPoint A ν y) (fun _ => 0) y =
KellyStochasticNetworks.dualObjective A ν C y := by sorry
end KellyLossNetworks.Primal
Source
Kelly, Loss networks, Ann. Appl. Probab. 1(3):319–378 (1991), DOI 10.1214/aoap/1177005872, pp. 327–328, §2.1, (2.2) and the display following it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.