TY - JOUR

T1 - Distributed optimization in an energy-constrained network

T2 - Analog versus digital communication schemes

AU - Razavi, Alireza

AU - Zhang, Wenbo

AU - Luo, Zhi Quan

PY - 2013/2/20

Y1 - 2013/2/20

N2 - We consider a distributed optimization problem whereby a network of n nodes, Sℓell; 1 n, wishes to minimize a common strongly convex function f(x), x=[1 xn]T, under the constraint that node Sℓ controls variable xℓ only. The nodes locally update their respective variables and periodically exchange their values with their neighbors over a set of predefined communication channels. Previous studies of this problem have focused mainly on the convergence issue and the analysis of convergence rate. In this study, we consider noisy communication channels and study the impact of communication energy on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an \epsilon-minimizer of f(x) in the mean square sense. For linear analog communication schemes, we prove that the communication energy to obtain an epsilon-minimizer of f(x) must grow at least at the rate of Ω (1ε), and this bound is tight when f is convex quadratic. Furthermore, we show that the same energy requirement can be reduced to O(21ε ) if a suitable digital communication scheme is used.

AB - We consider a distributed optimization problem whereby a network of n nodes, Sℓell; 1 n, wishes to minimize a common strongly convex function f(x), x=[1 xn]T, under the constraint that node Sℓ controls variable xℓ only. The nodes locally update their respective variables and periodically exchange their values with their neighbors over a set of predefined communication channels. Previous studies of this problem have focused mainly on the convergence issue and the analysis of convergence rate. In this study, we consider noisy communication channels and study the impact of communication energy on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an \epsilon-minimizer of f(x) in the mean square sense. For linear analog communication schemes, we prove that the communication energy to obtain an epsilon-minimizer of f(x) must grow at least at the rate of Ω (1ε), and this bound is tight when f is convex quadratic. Furthermore, we show that the same energy requirement can be reduced to O(21ε ) if a suitable digital communication scheme is used.

KW - Communication energy

KW - distributed optimization

KW - energy-constrained network

UR - http://www.scopus.com/inward/record.url?scp=84873917934&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873917934&partnerID=8YFLogxK

U2 - 10.1109/TIT.2012.2208550

DO - 10.1109/TIT.2012.2208550

M3 - Article

AN - SCOPUS:84873917934

VL - 59

SP - 1803

EP - 1817

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 3

M1 - 6238359

ER -