In this paper, we consider a network of processors that want to cooperatively solve a large-scale, convex optimization problem. Each processor has knowledge of a local cost function that depends only on a local variable. The goal is to minimize the sum of the local costs, while making the variables satisfy both local constraints and a global coupling constraint. We propose a simple, fully distributed algorithm, that works in a random, time-varying communication model, where at each iteration multiple edges are randomly drawn from an underlying graph. The algorithm is interpreted as a primal decomposition scheme applied to an equivalent problem reformulation. Almost sure convergence to the optimal cost of the original problem is proven by resorting to approaches from block subgradient methods. Specifically, the communication structure is mapped to a block structure, where the blocks correspond to the graph edges and are randomly selected at each iteration. Moreover, an almost sure asymptotic primal recovery property, with no averaging mechanisms, is shown. A numerical example corroborates the theoretical analysis.

Distributed Constraint-Coupled Optimization over Random Time-Varying Graphs via Primal Decomposition and Block Subgradient Approaches

Andrea camisa
;
Francesco Farina;Ivano Notarnicola;Giuseppe Notarstefano
2019

Abstract

In this paper, we consider a network of processors that want to cooperatively solve a large-scale, convex optimization problem. Each processor has knowledge of a local cost function that depends only on a local variable. The goal is to minimize the sum of the local costs, while making the variables satisfy both local constraints and a global coupling constraint. We propose a simple, fully distributed algorithm, that works in a random, time-varying communication model, where at each iteration multiple edges are randomly drawn from an underlying graph. The algorithm is interpreted as a primal decomposition scheme applied to an equivalent problem reformulation. Almost sure convergence to the optimal cost of the original problem is proven by resorting to approaches from block subgradient methods. Specifically, the communication structure is mapped to a block structure, where the blocks correspond to the graph edges and are randomly selected at each iteration. Moreover, an almost sure asymptotic primal recovery property, with no averaging mechanisms, is shown. A numerical example corroborates the theoretical analysis.
2019 IEEE 58th Conference on Decision and Control (CDC)
6374
6379
Andrea camisa, Francesco Farina, Ivano Notarnicola, Giuseppe Notarstefano
File in questo prodotto:
File Dimensione Formato  
2019cdc_Camisa_Distributed Constraint-Coupled Optimization over Random Time-Varying Graphs via Primal Decomposition and Block Subgradient Approaches.pdf

accesso riservato

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso riservato
Dimensione 321.83 kB
Formato Adobe PDF
321.83 kB Adobe PDF   Visualizza/Apri   Contatta l'autore
6pages_time_varying_primal_decomposition.pdf

embargo fino al 12/09/2020

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 631.78 kB
Formato Adobe PDF
631.78 kB 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/729706
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact