Distributed Optimization Using the Primal-Dual Method of Multipliers

被引:73
作者
Zhang, Guoqiang [1 ]
Heusdens, Richard [2 ]
机构
[1] Univ Technol Sydney, Sch Comp & Commun, Ultimo, NSW 2007, Australia
[2] Delft Univ Technol, Dept Microelect, Circuits & Syst Grp, NL-2628 CD Delft, Netherlands
来源
IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS | 2018年 / 4卷 / 01期
关键词
ADMM; distributed optimization; PDMM; sublinear convergence; GOSSIP ALGORITHMS; CONVERGENCE;
D O I
10.1109/TSIPN.2017.2672403
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, we propose the primal-dual method of multipliers (PDMM) for distributed optimization over a graph. In particular, we optimize a sum of convex functions defined over a graph, where every edge in the graph carries a linear equality constraint. In designing the new algorithm, an augmented primal-dual Lagrangian function is constructed which smoothly captures the graph topology. It is shown that a saddle point of the constructed function provides an optimal solution of the original problem. Further under both the synchronous and asynchronous updating schemes, PDMM has the convergence rate of O(1/K) (where K denotes the iteration index) for general closed, proper, and convex functions. Other properties of PDMM such as convergence speeds versus different parameter-settings and resilience to transmission failure are also investigated through the experiments of distributed averaging.
引用
收藏
页码:173 / 187
页数:15
相关论文
共 50 条
[21]   Accelerated Distributed Primal-Dual Dynamics Using Adaptive Synchronization [J].
Bansode, P. A. ;
Kosaraju, K. C. ;
Wagh, S. R. ;
Pasumarthy, R. ;
Singh, N. M. .
IEEE ACCESS, 2019, 7 :120424-120440
[22]   A Prediction-Correction Primal-Dual Algorithm for Distributed Optimization [J].
Paternain, Santiago ;
Fazlyab, Mahyar ;
Preciado, Victor M. ;
Ribeiro, Alejandro .
2019 AMERICAN CONTROL CONFERENCE (ACC), 2019, :835-841
[23]   A Primal-Dual Algorithm for Distributed Stochastic Optimization with Equality Constraints [J].
Du, Kai-Xin ;
Chen, Xing-Min .
2021 PROCEEDINGS OF THE 40TH CHINESE CONTROL CONFERENCE (CCC), 2021, :5586-5591
[24]   Primal-dual stochastic distributed algorithm for constrained convex optimization [J].
Niu, Youcheng ;
Wang, Haijing ;
Wang, Zheng ;
Xia, Dawen ;
Li, Huaqing .
JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 2019, 356 (16) :9763-9787
[25]   A Primal-Dual Forward-Backward Splitting Algorithm for Distributed Convex Optimization [J].
Li, Huaqing ;
Su, Enbing ;
Wang, Chengbo ;
Liu, Jiawei ;
Zheng, Zuqing ;
Wang, Zheng ;
Xia, Dawen .
IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, 2023, 7 (01) :278-284
[26]   A Stochastic Primal-Dual algorithm for Distributed Asynchronous Composite Optimization [J].
Bianchi, Pascal ;
Hachem, Walid ;
Iutzeler, Franck .
2014 IEEE GLOBAL CONFERENCE ON SIGNAL AND INFORMATION PROCESSING (GLOBALSIP), 2014, :732-736
[27]   Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization? [J].
Yuan, Kun ;
Xu, Wei ;
Ling, Qing .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2020, 68 :4466-4480
[28]   A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization [J].
Eisen, Mark ;
Mokhtari, Aryan ;
Ribeiro, Alejandro .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2019, 67 (23) :5983-5997
[29]   Derivation and Analysis of the Primal-Dual Method of Multipliers Based on Monotone Operator Theory [J].
Sherson, Thomas William ;
Heusdens, Richard ;
Kleijn, W. Bastiaan .
IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS, 2019, 5 (02) :334-347
[30]   A primal-dual active-set method for distributed model predictive control [J].
Koehler, Sarah ;
Danielson, Claus ;
Borrelli, Francesco .
OPTIMAL CONTROL APPLICATIONS & METHODS, 2017, 38 (03) :399-419