TY - GEN

T1 - Distributed optimization over time-varying directed graphs

AU - Nedíc, Angelia

AU - Olshevsky, Alex

PY - 2013

Y1 - 2013

N2 - We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a timevarying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O ( Int/√ t ), where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.

AB - We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a timevarying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O ( Int/√ t ), where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.

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

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

U2 - 10.1109/CDC.2013.6760975

DO - 10.1109/CDC.2013.6760975

M3 - Conference contribution

AN - SCOPUS:84902344212

SN - 9781467357173

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 6855

EP - 6860

BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 52nd IEEE Conference on Decision and Control, CDC 2013

Y2 - 10 December 2013 through 13 December 2013

ER -