TY - GEN
T1 - A distributed newton method for dynamic Network Utility Maximization with delivery contracts
AU - Wei, Ermin
AU - Ozdaglar, Asuman
AU - Eryilmaz, Atilla
AU - Jadbabaie, Ali
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84868524605&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84868524605&partnerID=8YFLogxK
U2 - 10.1109/CISS.2012.6310918
DO - 10.1109/CISS.2012.6310918
M3 - Conference contribution
AN - SCOPUS:84868524605
SN - 9781467331401
T3 - 2012 46th Annual Conference on Information Sciences and Systems, CISS 2012
BT - 2012 46th Annual Conference on Information Sciences and Systems, CISS 2012
T2 - 2012 46th Annual Conference on Information Sciences and Systems, CISS 2012
Y2 - 21 March 2012 through 23 March 2012
ER -