TY - JOUR
T1 - Distributed Discrete-Time Optimization in Multiagent Networks Using only Sign of Relative State
AU - Zhang, Jiaqi
AU - You, Keyou
AU - Basar, Tamer
N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 61722308, in part by the Tsinghua University Initiative Scientific Research Program, and in part by the ARL under cooperative agreement W911NF-17-2-0196.
Funding Information:
Manuscript received November 2, 2017; revised November 2, 2017 and April 7, 2018; accepted August 4, 2018. Date of publication December 4, 2018; date of current version May 27, 2019. This work was supported in part by the National Natural Science Foundation of China under Grant 61722308, in part by the Tsinghua University Initiative Scientific Research Program, and in part by the ARL under cooperative agreement W911NF-17-2-0196. Recommended by Associate Editor K. Cai. (Corresponding author: Keyou You.) J. Zhang and K. You are with the Department of Automation and the Beijing National Research Centre for Information Science and Technology, Tsinghua University, Beijing 100084, China (e-mail:, zjq16@mails. tsinghua.edu.cn; youky@tsinghua.edu.cn).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - This paper proposes distributed discrete-time algorithms to cooperatively solve an additive cost optimization problem in multiagent networks. The striking feature lies in the use of only the sign of relative state information between neighbors, which substantially differentiates our algorithms from others in the existing literature. We first interpret the proposed algorithms in terms of the penalty method in optimization theory and then perform nonasymptotic analysis to study convergence for static network graphs. Compared with the celebrated distributed subgradient algorithms, which, however, use the exact relative state information, the convergence speed is essentially not affected by the loss of information. We also study how introducing noise into the relative state information and randomly activated graphs affect the performance of our algorithms. Finally, we validate the theoretical results on a class of distributed quantile regression problems.
AB - This paper proposes distributed discrete-time algorithms to cooperatively solve an additive cost optimization problem in multiagent networks. The striking feature lies in the use of only the sign of relative state information between neighbors, which substantially differentiates our algorithms from others in the existing literature. We first interpret the proposed algorithms in terms of the penalty method in optimization theory and then perform nonasymptotic analysis to study convergence for static network graphs. Compared with the celebrated distributed subgradient algorithms, which, however, use the exact relative state information, the convergence speed is essentially not affected by the loss of information. We also study how introducing noise into the relative state information and randomly activated graphs affect the performance of our algorithms. Finally, we validate the theoretical results on a class of distributed quantile regression problems.
KW - Distributed optimization
KW - multiagent networks
KW - penalty method
KW - sign of relative state
KW - subgradient iterations
UR - http://www.scopus.com/inward/record.url?scp=85058117114&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058117114&partnerID=8YFLogxK
U2 - 10.1109/TAC.2018.2884998
DO - 10.1109/TAC.2018.2884998
M3 - Article
AN - SCOPUS:85058117114
SN - 0018-9286
VL - 64
SP - 2352
EP - 2367
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 6
M1 - 8558107
ER -