Distributed Multiagent Convex Optimization over Random Digraphs

Seyyed Shaho Alaviani, Nicola Elia

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-Time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm.

Original languageEnglish (US)
Article number8812738
Pages (from-to)986-998
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume65
Issue number3
DOIs
StatePublished - Mar 2020

Bibliographical note

Funding Information:
Manuscript received April 27, 2018; revised December 6, 2018; accepted April 20, 2019. Date of publication August 26, 2019; date of current version February 27, 2020. This work was supported by the National Science Foundation under Grant CCF-1320643 and Grant CNS-1239319 and AFOSR under Grant FA9550-15-1-0119. A preliminary version of the algorithm and results in this paper has appeared without proofs in [44]. Recommended by Associate Editor G. Pillonetto. (Corresponding author: Seyyed Shaho Alaviani.) S. S. Alaviani was with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50011 USA (e-mail:, shaho@alumni.iastate.edu).

Publisher Copyright:
© 1963-2012 IEEE.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

  • Asynchronous
  • distributed convex optimization
  • fixed-value point
  • minimization over fixed-value point set
  • random graphs

Fingerprint Dive into the research topics of 'Distributed Multiagent Convex Optimization over Random Digraphs'. Together they form a unique fingerprint.

Cite this