TY - GEN

T1 - Distributed optimization in an energy-constrained network using a digital communication scheme

AU - Razavi, Alireza

AU - Luo, Zhi Quan

PY - 2009/9/23

Y1 - 2009/9/23

N2 - We consider a distributed optimization problem where n nodes, S l, l ∈ {1, . . . , n}, wish to minimize a common strongly convex function f(x), x = [x1, . . . , xn]T , and suppose that node Sl only has control of variable xl. The nodes locally update their respective variables and periodically exchange their values over noisy channels. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an ∈-minimizer of f(x) in the mean square sense. In an earlier work, we considered analog communication schemes and proved that the communication energy must grow at the rate of Ω (∈-1) to obtain an ∈-minimizer of a convex quadratic function. In this paper, we consider digital communication schemes and propose a distributed algorithm which only requires communication energy of O((log ∈-1)3) to obtain an ∈-minimizer of f(x). Furthermore, the algorithm provided herein converges linearly. Thus, distributed optimization with digital communication schemes is significantly more energy efficient than with analog communication schemes.

AB - We consider a distributed optimization problem where n nodes, S l, l ∈ {1, . . . , n}, wish to minimize a common strongly convex function f(x), x = [x1, . . . , xn]T , and suppose that node Sl only has control of variable xl. The nodes locally update their respective variables and periodically exchange their values over noisy channels. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an ∈-minimizer of f(x) in the mean square sense. In an earlier work, we considered analog communication schemes and proved that the communication energy must grow at the rate of Ω (∈-1) to obtain an ∈-minimizer of a convex quadratic function. In this paper, we consider digital communication schemes and propose a distributed algorithm which only requires communication energy of O((log ∈-1)3) to obtain an ∈-minimizer of f(x). Furthermore, the algorithm provided herein converges linearly. Thus, distributed optimization with digital communication schemes is significantly more energy efficient than with analog communication schemes.

KW - Convergence

KW - Distributed optimization

KW - Energy constraint

KW - Sensor networks

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

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

U2 - 10.1109/ICASSP.2009.4960105

DO - 10.1109/ICASSP.2009.4960105

M3 - Conference contribution

AN - SCOPUS:70349205484

SN - 9781424423545

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 2401

EP - 2404

BT - 2009 IEEE International Conference on Acoustics, Speech, and Signal Processing - Proceedings, ICASSP 2009

T2 - 2009 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2009

Y2 - 19 April 2009 through 24 April 2009

ER -