Convergence Analysis of Quantized Primal-Dual Algorithms in Network Utility Maximization Problems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)284-297
Journal / PublicationIEEE Transactions on Control of Network Systems
Volume5
Issue number1
Online published8 Sep 2016
Publication statusPublished - Mar 2018
Externally publishedYes

Abstract

This paper investigates the asymptotic and nonasymptotic behavior of the quantized primal-dual (PD) algorithm in network utility maximization (NUM) problems, in which a group of agents maximizes the sum of their individual concave objective functions under linear constraints. In the asymptotic scenario, we use the information-theoretic notion of differential entropy power to establish universal bounds on the maximum exponential convergence rates of joint PD, primal and dual variables under optimum-achieving quantization schemes. These results provide tradeoffs between the speed of exponential convergence, the agents' objective functions, the communication bit rates, and the number of agents and constraints. In the nonasymptotic scenario, we obtain lower bounds on the mean square distance of joint PD, primal and dual variables from the optimal solution at any time instant. These bounds hold regardless of the quantization scheme used.

Research Area(s)

  • Entropy power method, network utility maximization (NUM), primal-dual (PD) algorithm, quantized communications