Equations (2.4)–(2.5): complementary feasibility gives optima
ProvedKellyLossNetworks.Primal.complementary_sufficesconvex-dualityloss-networksoperations-researchp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with . If , , and
then is feasible and maximizes the primal objective, while minimizes the dual objective over the nonnegative orthant. This is the sufficiency of the feasibility and complementary slackness conditions stated in (2.4)–(2.5).
Preamble
import Mathlib import Definitions.Def_KellyLossNetworks_Primal_Problem
Formal statement
namespace KellyLossNetworks.Primal
/-- Kelly, *Loss networks* (1991), §2.1, p. 328, (2.4)–(2.5) and the sentence before them. -/
theorem complementary_suffices {J R : ℕ} (A : Fin J → Fin R → ℕ)
(ν : Fin R → ℝ) (C : Fin J → ℕ) (hν : ∀ r, 0 < ν r)
(y : Fin J → ℝ) (h : complementary A ν C y) :
(primalPoint A ν y ∈ primalFeasible A C ∧
IsMaxOn (primalObjective ν) (primalFeasible A C) (primalPoint A ν y)) ∧
IsDualOpt 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, p. 328, §2.1, (2.4)–(2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.