Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs
We consider a distributed constrained optimization problem over graphs, where cost function of each agent is private. Moreover, we assume that the graphs are time-varying and directed. In order to address such problem, a fully decentralized stochastic subgradient projection algorithm is proposed ove...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/8030792 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849692563060031488 |
|---|---|
| author | Junlong Zhu Ping Xie Mingchuan Zhang Ruijuan Zheng Ling Xing Qingtao Wu |
| author_facet | Junlong Zhu Ping Xie Mingchuan Zhang Ruijuan Zheng Ling Xing Qingtao Wu |
| author_sort | Junlong Zhu |
| collection | DOAJ |
| description | We consider a distributed constrained optimization problem over graphs, where cost function of each agent is private. Moreover, we assume that the graphs are time-varying and directed. In order to address such problem, a fully decentralized stochastic subgradient projection algorithm is proposed over time-varying directed graphs. However, since the graphs are directed, the weight matrix may not be a doubly stochastic matrix. Therefore, we overcome this difficulty by using weight-balancing technique. By choosing appropriate step-sizes, we show that iterations of all agents asymptotically converge to some optimal solutions. Further, by our analysis, convergence rate of our proposed algorithm is O(ln Γ/Γ) under local strong convexity, where Γ is the number of iterations. In addition, under local convexity, we prove that our proposed algorithm can converge with rate O(ln Γ/Γ). In addition, we verify the theoretical results through simulations. |
| format | Article |
| id | doaj-art-ea2ddcf83adf4df4b13996d23ee248bf |
| institution | DOAJ |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-ea2ddcf83adf4df4b13996d23ee248bf2025-08-20T03:20:39ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/80307928030792Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed GraphsJunlong Zhu0Ping Xie1Mingchuan Zhang2Ruijuan Zheng3Ling Xing4Qingtao Wu5Information Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaInformation Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaInformation Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaInformation Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaInformation Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaInformation Engineering College, Henan University of Science and Technology, Luoyang 471023, ChinaWe consider a distributed constrained optimization problem over graphs, where cost function of each agent is private. Moreover, we assume that the graphs are time-varying and directed. In order to address such problem, a fully decentralized stochastic subgradient projection algorithm is proposed over time-varying directed graphs. However, since the graphs are directed, the weight matrix may not be a doubly stochastic matrix. Therefore, we overcome this difficulty by using weight-balancing technique. By choosing appropriate step-sizes, we show that iterations of all agents asymptotically converge to some optimal solutions. Further, by our analysis, convergence rate of our proposed algorithm is O(ln Γ/Γ) under local strong convexity, where Γ is the number of iterations. In addition, under local convexity, we prove that our proposed algorithm can converge with rate O(ln Γ/Γ). In addition, we verify the theoretical results through simulations.http://dx.doi.org/10.1155/2019/8030792 |
| spellingShingle | Junlong Zhu Ping Xie Mingchuan Zhang Ruijuan Zheng Ling Xing Qingtao Wu Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs Complexity |
| title | Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs |
| title_full | Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs |
| title_fullStr | Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs |
| title_full_unstemmed | Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs |
| title_short | Distributed Stochastic Subgradient Projection Algorithms Based on Weight-Balancing over Time-Varying Directed Graphs |
| title_sort | distributed stochastic subgradient projection algorithms based on weight balancing over time varying directed graphs |
| url | http://dx.doi.org/10.1155/2019/8030792 |
| work_keys_str_mv | AT junlongzhu distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs AT pingxie distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs AT mingchuanzhang distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs AT ruijuanzheng distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs AT lingxing distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs AT qingtaowu distributedstochasticsubgradientprojectionalgorithmsbasedonweightbalancingovertimevaryingdirectedgraphs |