In this paper, we consider a novel partitioned framework for distributed optimization in peer-to-peer networks. In several important applications, the agents of a network have to solve an optimization problem with two key features: i) the dimension of the decision variable depends on the network size, and ii) cost function and constraints have a sparsity structure related to the communication graph. For this class of problems, a straightforward application of existing consensus methods would show two inefficiencies: poor scalability and redundancy of shared information. We propose an asynchronous distributed algorithm, based on dual decomposition and coordinate methods, to solve partitioned optimization problems. We show that by exploiting the problem structure, the solution can be partitioned among the nodes, so that each node just stores a local copy of a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small-scale local problem.

Distributed Partitioned Big-Data Optimization via Asynchronous Dual Decomposition

Notarnicola, Ivano
;
Notarstefano, Giuseppe
2018

Abstract

In this paper, we consider a novel partitioned framework for distributed optimization in peer-to-peer networks. In several important applications, the agents of a network have to solve an optimization problem with two key features: i) the dimension of the decision variable depends on the network size, and ii) cost function and constraints have a sparsity structure related to the communication graph. For this class of problems, a straightforward application of existing consensus methods would show two inefficiencies: poor scalability and redundancy of shared information. We propose an asynchronous distributed algorithm, based on dual decomposition and coordinate methods, to solve partitioned optimization problems. We show that by exploiting the problem structure, the solution can be partitioned among the nodes, so that each node just stores a local copy of a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small-scale local problem.
Notarnicola, Ivano; Carli, Ruggero; Notarstefano, Giuseppe
File in questo prodotto:
File Dimensione Formato  
asynch_pb_dual_decomposition_post_reviewed.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 1.41 MB
Formato Adobe PDF
1.41 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/671783
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 13
social impact