Valls, Victor and Leith, Douglas J. (2014) On the Relationship Between Queues and Multipliers. In: 52nd Annual Allerton Conference on Communication, Control, and Computing, 1-3 October 2014, Allerton Retreat Center Monticello, Illinois.

Preview

Download (386kB) | Preview

Abstract

We show that the occupancy of appropriate queues can be used as a surrogate for Lagrange multipliers in convex optimisation. Our analysis uses only elementary methods, and is not asymptotic in nature. One immediate consequence is that in network problems the scaled link queue occupancy can be used as multipliers when calculating the dual function. Conversely, the connection with multipliers casts light on the link queue behaviour under optimal decision-making (not just max-weight scheduling). Namely, on links corresponding to active constraints the queue occupancy necessarily grows as step size α is reduced. Importantly, our analysis encompasses nonlinear constraints, and so generalises analysis beyond conventional queueing networks.

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	This material is based upon works supported by the Science Foundation Ireland under Grant No. 11/PI/1177.
Keywords:	convex optimisation; subgradient methods; maxweight scheduling;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	5962
Depositing User:	Professsor Douglas Leith
Date Deposited:	12 Mar 2015 16:35
Refereed:	Yes
Funders:	Science Foundation Ireland (SFI)
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads