Finite-Time Consensus Dual Algorithm for Distributed Optimization over Digraphs

Wei Jiang*, Themistoklis Charalambous*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

46 Downloads (Pure)

Abstract

In this paper, we solve the convex distributed optimization problems, which include unconstrained optimization and a special constrained problem commonly known as a resource allocation problem, over a network of agents among which the communication can be represented by directed graphs (digraphs), by using the finite-time consensus-based and dual-based first-order gradient descent (GD) techniques. The key point is that a special consensus matrix is utilized for problem reformulation to make our dual-based algorithm suitable for digraphs. By the property of distributed finite-time exact (not approximate) consensus, the classical centralized optimization techniques (e.g., Nesterov accelerated GD) can be embedded into our dual-based algorithm conveniently, which means our distributed algorithm can inherit performance of classical centralized algorithms that has been proved to have optimal convergence performance. As a result, our proposed algorithm has faster convergence rate related to the optimization iteration number compared with other distributed optimization algorithms in literature. Since there are finite consensus communication steps inside each consensus process, when the time needed to communicate values between two neighbors is less than a threshold of the time needed to perform local computations, our proposed algorithm is also faster related to the time, as demonstrated in the simulations.

Original languageEnglish
Title of host publicationIFAC-PapersOnLine
EditorsHideaki Ishii, Yoshio Ebihara, Jun-ichi Imura, Masaki Yamakita
PublisherElsevier
Pages1926-1931
Number of pages6
Edition2
ISBN (Electronic)9781713872344
DOIs
Publication statusPublished - 1 Jul 2023
MoE publication typeA4 Conference publication
EventIFAC World Congress - Yokohama, Japan
Duration: 9 Jul 202314 Jul 2023
Conference number: 22

Publication series

NameIFAC-PapersOnLine
Number2
Volume56
ISSN (Electronic)2405-8963

Conference

ConferenceIFAC World Congress
Country/TerritoryJapan
CityYokohama
Period09/07/202314/07/2023

Keywords

  • digraphs
  • Distributed optimization
  • dual
  • finite-time consensus

Fingerprint

Dive into the research topics of 'Finite-Time Consensus Dual Algorithm for Distributed Optimization over Digraphs'. Together they form a unique fingerprint.

Cite this