A distributed newton method for dynamic Network Utility Maximization with delivery contracts
Ermin Wei, Asuman Ozdaglar, Atilla Eryılmaz et al. · Conference on Information Sciences and Systems · 2012
The standard Network Utility Maximization (NUM) problem has a static formulation, which fails to capture the temporal dynamics in modern networks. This work considers a dynamic version of the NUM problem by introducing additional constraints, referred to as delivery contracts. Each delivery contract specifies the amount of information that needs to be delivered over a certain time interval for a particular source and is motivated by applications such as video streaming or webpage loading. The existing distributed algorithms for the Network Utility Maximization problems are either only applicable for the static version of the problem or rely on dual decomposition and first-order (gradient or subgradient) methods, which are slow in convergence. In this work, we develop a distributed Newton-type algorithm for the dynamic problem, which is implemented in the primal space and involves computing the dual variables at each primal step. We propose a novel distributed iterative approach for calculating the dual variables with finite termination based on matrix splitting techniques. It can be shown that if the error level in the Newton direction (resulting from finite termination of dual iterations) is below a certain threshold, then the algorithm achieves local quadratic convergence rate to an error neighborhood of the optimal solution in the primal space. Simulation results demonstrate significant convergence rate improvement of our algorithm, relative to the existing first-order methods based on dual decomposition.
Cited by 12 works. doi:10.1109/ciss.2012.6310918
Authors
References
- Convex Optimization
- Interior-Point Polynomial Algorithms in Convex Programming
- Rate control for communication networks: shadow prices, proportional fairness and stability
- Charging and rate control for elastic traffic
- Rate control for communication networks: shadow prices, proportional fairness and stability
- The Linear Complementarity Problem
- Optimization flow control. I. Basic algorithm and convergence
- Fair end-to-end window-based congestion control
- Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures
- The Linear Complementarity Problem.