MURAL - Maynooth University Research Archive Library



    On the Relationship Between Queues and Multipliers


    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.

    [thumbnail of DL-Multipliers.pdf]
    Preview
    Text
    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://mural.maynoothuniversity.ie/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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads