Continuous-time distributed optimization of homogenous dynamics

Guodong Shi, Alexandre Proutiere, Karl Henrik Johansson

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

1 Citation (Scopus)

Abstract

This paper makes an attempt to explore the fundamental properties of distributed methods for minimizing a sum of objective functions with each component only known to a particular node, given a certain level of node knowledge and computation capacity. The information each node receives from its neighbors can be any nonlinear function of its neighbors' states as long as the function takes value zero within the local consensus manifold. Each node also observes the gradient of its own objective function at its current state. The update dynamics of each node is a first-order integrator. The admissible control input of each node is homogeneous, given by a binary function with each variable corresponding to the neighboring term and the gradient term, respectively. The function determining the control law is assumed to be injective when the first variable is fixed to zero. It is proven that there exists a control rule which guarantees global optimal consensus if and only if the solution sets of the local objectives admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a simple control rule that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved by a simple control rule as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for distributed optimization using consensus processing to connect the information over the nodes.

Original languageEnglish
Title of host publication2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PublisherIEEE Computer Society
Pages520-527
Number of pages8
ISBN (Print)9781479934096
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States
Duration: 2 Oct 20134 Oct 2013

Publication series

Name2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Conference

Conference51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Country/TerritoryUnited States
CityMonticello, IL
Period2/10/134/10/13

Fingerprint

Dive into the research topics of 'Continuous-time distributed optimization of homogenous dynamics'. Together they form a unique fingerprint.

Cite this