Distributed discrete-time optimization by exchanging one bit of information

Jiaqi Zhang, Keyou You, Tamer Başar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper proposes a distributed discrete-time algorithm to solve an additive cost optimization problem over undirected deterministic or time-varying graphs. Different from most previous methods that require to exchange exact states between nodes, each node in our algorithm needs only the sign of the relative state between its neighbors, which is clearly one bit of information. Our analysis is based on optimization theory rather than Lyapunov theory or algebraic graph theory. The latter is commonly used in existing literature, especially in the continuous-time algorithm design, and is difficult to apply in our case. Besides, an optimization-theory-based analysis may make our results more extendible. In particular, our convergence proofs are based on the convergences of the subgradient method and the stochastic subgradient method. Moreover, the convergence rate of our algorithm can vary from O(1/\ln(k)) to O(1/√k), depending on the choice of the stepsize. A quantile regression problem is included to illustrate the performance of our algorithm using simulations.

Original languageEnglish (US)
Title of host publication2018 Annual American Control Conference, ACC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2065-2070
Number of pages6
ISBN (Print)9781538654286
DOIs
StatePublished - Aug 9 2018
Event2018 Annual American Control Conference, ACC 2018 - Milwauke, United States
Duration: Jun 27 2018Jun 29 2018

Publication series

NameProceedings of the American Control Conference
Volume2018-June
ISSN (Print)0743-1619

Other

Other2018 Annual American Control Conference, ACC 2018
CountryUnited States
CityMilwauke
Period6/27/186/29/18

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Distributed discrete-time optimization by exchanging one bit of information'. Together they form a unique fingerprint.

  • Cite this

    Zhang, J., You, K., & Başar, T. (2018). Distributed discrete-time optimization by exchanging one bit of information. In 2018 Annual American Control Conference, ACC 2018 (pp. 2065-2070). [8431279] (Proceedings of the American Control Conference; Vol. 2018-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/ACC.2018.8431279