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
DL-Multipliers.pdf
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: | https://mu.eprints-hosting.org/id/eprint/5962 |
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)
Downloads
Downloads per month over past year