Title :
On the relationship between queues and multipliers
Author :
Valls, V. ; Leith, D.J.
fDate :
Sept. 30 2014-Oct. 3 2014
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.
Keywords :
convex programming; decision making; gradient methods; queueing theory; Lagrange multipliers; active constraints; appropriate queue occupancy; convex optimisation; dual function calculation; elementary methods; link queue behaviour; max-weight scheduling; network problems; nonlinear constraints; optimal decision-making; scaled link queue occupancy; subgradient methods; Convex functions; Decision making; Optimization; Queueing analysis; Standards; Stochastic processes; Vectors; convex optimisation; max-weight scheduling; subgradient methods;
Conference_Titel :
Communication, Control, and Computing (Allerton), 2014 52nd Annual Allerton Conference on
Conference_Location :
Monticello, IL
DOI :
10.1109/ALLERTON.2014.7028463