A divide-and-conquer algorithm for distributed optimization on networks

Distributed algorithms (68W15) Deterministic network models in operations research (90B10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Applications of graph theory to circuits and networks (94C15)

Abstract: In this paper, we consider networks with topologies described by some connected undirected graph

m a t h c a l G = (V, E)

and with some agents (fusion centers) equipped with processing power and local peer-to-peer communication, and optimization problem

with local objective functions

f_{i}

depending only on neighboring variables of the vertex

i i n V

. We introduce a divide-and-conquer algorithm to solve the above optimization problem in a distributed and decentralized manner. The proposed divide-and-conquer algorithm has exponential convergence, its computational cost is almost linear with respect to the size of the network, and it can be fully implemented at fusion centers of the network. Our numerical demonstrations also indicate that the proposed divide-and-conquer algorithm has superior performance than popular decentralized optimization methods do for the least squares problem with/without

e l l^{1}

penalty.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: A divide-and-conquer algorithm for distributed optimization on networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6122629)