Lemma A.1, p. 1945 — under C.1, co(S) is closed downward: c ∈ co(S), 0 ≤ x ≤ c ⇒ x ∈ co(S)
ProvedConstrainedQueueing.Nonstationary.lemma_A_1constrained-queueingconvex-hulldownward-closedp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a constraint set of activation sets of servers satisfying assumption C.1 (every subset of an activation set is an activation set), and let be the convex hull of the activation vectors of . Then is closed downward in the nonnegative orthant: for every and every ,
In the proof of Lemma 4.1 this is what turns a maximum flow, whose server components are bounded by a point of , into a point of itself.
Formalization Note. The vectors are Fin N → ℝ with the componentwise order. C.1 is the only hypothesis; nonemptiness of follows from .
Preamble
import Mathlib import Definitions.Def_ConstrainedQueueing_Nonstationary_Model
Formal statement
namespace ConstrainedQueueing.Nonstationary
/-- Lemma A.1 (p. 1945): under C.1, if a vector `c` belongs to `co(S)`, then every vector `x`
with `0 ≤ x ≤ c` (componentwise) belongs to `co(S)` as well. -/
theorem lemma_A_1 {L N : ℕ} (net : Network L N) (hC1 : C1 net) :
∀ c ∈ coS net, ∀ x : Fin N → ℝ, 0 ≤ x → x ≤ c → x ∈ coS net := by sorry
end ConstrainedQueueing.Nonstationary
Source
Tassiulas and Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Trans. Automat. Control 37(12) (1992), p. 1945, Appendix, Lemma A.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.