Proof of Theorem 5, p. 215 — x* = x̃ + x̂ ∈ 𝒜 and Rx* = Rx̂ ≥ δe with δ > 0
ProvedMaxPressure.FluidStab.xstar_mem_allocallocationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1static-planning-lpstochastic-processing-network
Let be a feasible solution of the static planning LP (9)–(13) with . Let satisfy and for every input processor . Then there is a scaling factor such that, writing :
- for every service processor ;
- belongs to the allocation set ;
- ;
- there is with , where is the vector of ones:
In the paper . The allocation serves as the comparison allocation in the Lyapunov argument of Theorem 5: it is feasible and drains every buffer at rate at least .
Formalization Note The constant is stated existentially (the minimum over an empty index set would be undefined when ); any with serves the proof. The statement does not need the standing assumptions, which are therefore not hypotheses.
Preamble
import Mathlib import Definitions.Def_MaxPressure_FluidStab_Network
Formal statement
namespace MaxPressure.FluidStab
open Matrix
/-- Proof of Theorem 5, App. B, p. 215: let `(x̃, ρ)` be feasible for the LP (9)–(13) with
`ρ < 1`, and let `x̂ ≥ 0` satisfy `Rx̂ > 0` and `∑_j A_kj x̂_j = 0` for each input processor `k`.
Then `x̂` can be scaled (by some `c > 0`) so that `∑_j A_kj x̂_j ≤ 1 − ρ` for each service
processor `k`, and for the scaled `x̂` the allocation `x* = x̃ + x̂` lies in `𝒜`,
`Rx* = Rx̂`, and `Rx* ≥ εe` for some `ε > 0` (the paper's `δ = min_i ∑_j R_ij x̂_j`). -/
theorem xstar_mem_alloc {I J K : ℕ} (N : Network I J K)
(xt : Fin J → ℝ) (ρ : ℝ) (hρ : ρ < 1) (hLP : LPFeasible N xt ρ)
(xh : Fin J → ℝ) (hxh : ∀ j, 0 ≤ xh j) (hpos : ∀ i, 0 < (R N *ᵥ xh) i)
(hin : ∀ k, N.inputProc k → ∑ j, N.A k j * xh j = 0) :
∃ c : ℝ, 0 < c ∧
(∀ k, ¬ N.inputProc k → ∑ j, N.A k j * (c • xh) j ≤ 1 - ρ) ∧
xt + c • xh ∈ allocSet N ∧
R N *ᵥ (xt + c • xh) = R N *ᵥ (c • xh) ∧
∃ ε : ℝ, 0 < ε ∧ ∀ i, ε ≤ (R N *ᵥ (xt + c • xh)) i := by sorry
end MaxPressure.FluidStab
Source
Dai & Lin, Maximum pressure policies in stochastic processing networks, Oper. Res. 53(2) (2005), p. 215, proof of Theorem 5 (App. B), sentences 5–7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.