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.

    [img]
    Preview
    Download (386kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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)

      View Item Item control page

      Downloads

      Downloads per month over past year

      Origin of downloads