TY - GEN
T1 - Convergence analysis of quantized primal-dual algorithm in quadratic network utility maximization problems
AU - Nekouei, Ehsan
AU - Nair, Girish
AU - Alpcan, Tansu
PY - 2015/12
Y1 - 2015/12
N2 - This paper examines the effect of quantized communications on the convergence behavior of the primal-dual algorithm in quadratic network utility maximization problems with linear equality constraints. In our set-up, it is assumed that the primal variables are updated by individual agents, whereas the dual variables are updated by a central entity, called system, which has access to the parameters quantifying the system-wide constraints. The notion of differential entropy power is used to establish a universal lower bound on the rate of exponential mean square convergence of the primal-dual algorithm under quantized message passing between agents and the system. The lower bound is controlled by the average aggregate data rate under the quantization, the curvature of the utility functions of agents, the number of agents and the number of constraints. An adaptive quantization scheme is proposed under which the primal-dual algorithm converges to the optimal solution despite quantized communications between agents and the system. Finally, the rate of exponential convergence of the primal-dual algorithm under the proposed quantization scheme is numerically studied.
AB - This paper examines the effect of quantized communications on the convergence behavior of the primal-dual algorithm in quadratic network utility maximization problems with linear equality constraints. In our set-up, it is assumed that the primal variables are updated by individual agents, whereas the dual variables are updated by a central entity, called system, which has access to the parameters quantifying the system-wide constraints. The notion of differential entropy power is used to establish a universal lower bound on the rate of exponential mean square convergence of the primal-dual algorithm under quantized message passing between agents and the system. The lower bound is controlled by the average aggregate data rate under the quantization, the curvature of the utility functions of agents, the number of agents and the number of constraints. An adaptive quantization scheme is proposed under which the primal-dual algorithm converges to the optimal solution despite quantized communications between agents and the system. Finally, the rate of exponential convergence of the primal-dual algorithm under the proposed quantization scheme is numerically studied.
UR - http://www.scopus.com/inward/record.url?scp=84962034290&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84962034290&origin=recordpage
U2 - 10.1109/CDC.2015.7402616
DO - 10.1109/CDC.2015.7402616
M3 - 32_Refereed conference paper (with ISBN/ISSN)
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 2655
EP - 2660
BT - 2015 54th IEEE Conference on Decision and Control (CDC)
PB - IEEE
T2 - 54th IEEE Conference on Decision and Control, CDC 2015
Y2 - 15 December 2015 through 18 December 2015
ER -