Delay reduction via Lagrange multipliers in stochastic network optimization

DOI10.1109/TAC.2010.2067371zbMATH Open1368.90029arXiv0904.3795MaRDI QIDQ5347674FDOQ5347674

Michael J. Neely, Longbo Huang

Publication date: 25 August 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: In this paper, we consider the problem of reducing network delay in stochastic network utility optimization problems. We start by studying the recently proposed quadratic Lyapunov function based algorithms (QLA). We show that for every stochastic problem, there is a corresponding emph{deterministic} problem, whose dual optimal solution "exponentially attracts" the network backlog process under QLA. In particular, the probability that the backlog vector under QLA deviates from the attractor is exponentially decreasing in their Euclidean distance. This not only helps to explain how QLA achieves the desired performance but also suggests that one can roughly "subtract out" a Lagrange multiplier from the system induced by QLA. We thus develop a family of emph{Fast Quadratic Lyapunov based Algorithms} (FQLA) that achieve an $[O(1/V),O(lo{g}^2(V))]$ performance-delay tradeoff for problems with a discrete set of action options, and achieve a square-root tradeoff for continuous problems. This is similar to the optimal performance-delay tradeoffs achieved in prior work by Neely (2007) via drift-steering methods, and shows that QLA algorithms can also be used to approach such performance. These results highlight the "network gravity" role of Lagrange Multipliers in network scheduling. This role can be viewed as the counterpart of the "shadow price" role of Lagrange Multipliers in flow regulation for classic flow-based network problems.

Full work available at URL: https://arxiv.org/abs/0904.3795

Mathematics Subject Classification ID

Stochastic programming (90C15) Stochastic network models in operations research (90B15)

Cited In (3)

• Title not available (Why is that?)
• Lagrange dual bound computation for stochastic service network design
• Stability and probability. I: Convergence for queueing networks via Lyapunov optimization

   Recommendations

• Stochastic network optimization with application to communication and queueing systems 👍 👎
• Lagrange dual bound computation for stochastic service network design 👍 👎
• Optimization Over Time-Varying Networks and Unbounded Information Delays 👍 👎
• Title not available (Why is that?) 👍 👎
• Revisiting Lagrangian relaxation for network design 👍 👎
• A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints 👍 👎
• Distributed Stochastic Optimization with Large Delays 👍 👎
• Optimising waiting at nodes in time-dependent networks: cost functions and applications 👍 👎
• On Throughput Optimality With Delayed Network-State Information 👍 👎

This page was built for publication: Delay reduction via Lagrange multipliers in stochastic network optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347674)