
-
Previous Article
Stability of ground state for the Schrödinger-Poisson equation
- JIMO Home
- This Issue
-
Next Article
Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound
Distributed convex optimization with coupling constraints over time-varying directed graphs†
1. | School of Finance and Economics, Yangtze Normal University, Chongqing, 408100, China |
2. | Department of Mathematics and Statistics, Curtin University, Bentley, WA, 6102, Australia |
3. | School of Mathematical Sciences, Chongqing Normal University, Chongqing, 400047, China |
This paper considers a distributed convex optimization problem over a time-varying multi-agent network, where each agent has its own decision variables that should be set so as to minimize its individual objective subject to local constraints and global coupling constraints. Over directed graphs, we propose a distributed algorithm that incorporates the push-sum protocol into dual sub-gradient methods. Under the convexity assumption, the optimality of primal and dual variables, and the constraint violation are first established. Then the explicit convergence rates of the proposed algorithm are obtained. Finally, numerical experiments on the economic dispatch problem are provided to demonstrate the efficacy of the proposed algorithm.
References:
[1] |
N. S. Aybat and E. Y. Hamedani, Distributed primal-dual method for multi-agent sharing problem with conic constraints, 2016 50th Asilomar Conference on Signals, Systems and Computers, (2016), 777–782.
doi: 10.1109/ACSSC.2016.7869152. |
[2] |
N. S. Aybat and E. Y. Hamedani,
A distributed ADMM-like method for resource sharing over time-varying networks, SIAM J. Optim., 29 (2019), 3036-3068.
doi: 10.1137/17M1151973. |
[3] |
B. Baingana, G. Mateos and G. B. Giannakis,
Proximal-gradient algorithms for tracking cascades over social networks, IEEE Journal of Selected Topics in Signal Processing, 8 (2014), 563-575.
doi: 10.1109/JSTSP.2014.2317284. |
[4] |
A. Beck, A. Nedić, A. Ozdaglar and M. Teboulle,
An $O(1/k)$ gradient method for network resource allocation problems, IEEE Trans. Control Netw. Syst., 1 (2014), 64-73.
doi: 10.1109/TCNS.2014.2309751. |
[5] |
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
doi: 10.1017/CBO9780511804441.![]() ![]() |
[6] |
T.-H. Chang, A. Nedić and A. Scaglione,
Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Trans. Automat. Control, 59 (2014), 1524-1538.
doi: 10.1109/TAC.2014.2308612. |
[7] |
T.-H. Chang, M. Hong and X. Wang,
Multi-agent distributed optimization via inexact consensus ADMM, IEEE Trans. Signal Process., 63 (2015), 482-497.
doi: 10.1109/TSP.2014.2367458. |
[8] |
T.-H. Chang,
A proximal dual consensus ADMM method for multi-agent constrained optimization, IEEE Trans. Signal Process., 64 (2016), 3719-3734.
doi: 10.1109/TSP.2016.2544743. |
[9] |
J. C. Duchi, A. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Trans. Automat. Control, 57 (2012) 592–606.
doi: 10.1109/TAC.2011.2161027. |
[10] |
A. Falsone, K. Margellos, S. Garatti and M. Prandini,
Dual decomposition for multi-agent distributed optimization with coupling constraints, Automatica J. IFAC, 84 (2017), 149-158.
doi: 10.1016/j.automatica.2017.07.003. |
[11] |
X. S. Han, H. B. Gooi and D. S. Kirschen,
Dynamic economic dispatch: Feasible and optimal solutions, 2001 Power Engineering Society Summer Meeting. Conference Proceedings, 16 (2001), 22-28.
doi: 10.1109/PESS.2001.970332. |
[12] |
J. Li, C. Wu, Z. Wu and Q. Long,
Gradient-free method for nonsmooth distributed optimization, J. Global Optim., 61 (2015), 325-340.
doi: 10.1007/s10898-014-0174-2. |
[13] |
J. Li, G. Chen, Z. Dong and Z. Wu,
A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Comput. Optim. Appl., 64 (2016), 671-697.
doi: 10.1007/s10589-016-9826-0. |
[14] |
J. Li, C. Gu, Z. Wu and C. Wu, Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks, Complexity, 2017 (2017), Article ID 3610283, 10 pp.
doi: 10.1155/2017/3610283. |
[15] |
P. Di Lorenzo and G. Scutari,
NEXT: In-network nonconvex optimization, IEEE Trans. Signal Inform. Process. Netw., 2 (2016), 120-136.
doi: 10.1109/TSIPN.2016.2524588. |
[16] |
G. Mateos and G. B. Giannakis,
Distributed recursive least-squares: Stability and performance analysis, IEEE Trans. Signal Process., 60 (2012), 3740-3754.
doi: 10.1109/TSP.2012.2194290. |
[17] |
D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick and J. Lavaei, A survey of distributed optimization and control algorithms for electric power systems, IEEE Transactions on Smart Grid, 8 (2017), 2941-2962. Google Scholar |
[18] |
A. Nedić and A. Ozdaglar,
Distributed subgradient methods for multi-agent optimization, IEEE Trans. Automat. Control, 54 (2009), 48-61.
doi: 10.1109/TAC.2008.2009515. |
[19] |
A. Nedić and A. Olshevsky,
Distributed optimization over time-varying directed graphs, IEEE Trans. Automat. Control, 60 (2015), 601-615.
doi: 10.1109/TAC.2014.2364096. |
[20] |
A. Nedić, A. Olshevsky and W. Shi,
Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM J. Optim., 27 (2017), 2597-2633.
doi: 10.1137/16M1084316. |
[21] |
B. T. Polyak, Introduction to Optimization, Optimization Software, Inc., Publications Division, New York, 1987. |
[22] |
S. S. Ram, A. Nedić and V. V. Veeravalli,
Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory Appl., 147 (2010), 516-545.
doi: 10.1007/s10957-010-9737-7. |
[23] |
W. Shi, Q. Ling, K. Yuan, G. Wu and W. Yin,
On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Signal Process., 62 (2014), 1750-1761.
doi: 10.1109/TSP.2014.2304432. |
[24] |
W. Shi, Q. Ling, G. Wu and W. Yin,
EXTRA: An exact first-order algorithm for decentralized consensus optimization, SIAM J. Optim., 25 (2015), 944-966.
doi: 10.1137/14096668X. |
[25] |
K. I. Tsianos, S. Lawlor and M. G. Rabbat, Push-sum distributed dual averaging for convex optimization, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), (2012), 5453–5458.
doi: 10.1109/CDC.2012.6426375. |
[26] |
S. Wang and C. Li,
Distributed robust optimization in networked system, IEEE Transactions on Cybernetics, 47 (2017), 2321-2333.
doi: 10.1109/TCYB.2016.2613129. |
[27] |
X. Xia and A. M. Elaiw,
Optimal dynamic economic dispatch of generation: A review, Electric Power Systems Research, 80 (2010), 975-986.
doi: 10.1016/j.epsr.2009.12.012. |
[28] |
C. Yang, Y. Xu, L. Zhou and Y. Sun, Model-free composite control of flexible manipulators based on adaptive dynamic programming, Complexity, 2018 (2018), Article ID 9720309, 9 pp.
doi: 10.1155/2018/9720309. |
[29] |
D. Yuan, S. Xu and H. Zhao, Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41 (2011), 1715-1724. Google Scholar |
[30] |
D. Yuan, D. W. Ho and Y. Hong,
On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints, SIAM J. Control Optim., 54 (2016), 2872-2892.
doi: 10.1137/15M1048896. |
[31] |
D. Yuan, D. W. C. Ho and S. Xu,
Regularized primal-dual subgradient method for distributed constrained optimization, IEEE Transactions on Cybernetics, 46 (2016), 2109-2118.
doi: 10.1109/TCYB.2015.2464255. |
[32] |
Y. Zhang and G. B. Giannakis, Distributed stochastic market clearing with high-penetration wind power, IEEE Transactions on Power Systems, 31 (2016), 895-906. Google Scholar |
[33] |
Z. Zhang and M. Y. Chow,
Convergence analysis of the incremental cost consensus algorithm under different communication network topologies in a smart grid, IEEE Transactions on Power Systems, 27 (2012), 1761-1768.
doi: 10.1109/TPWRS.2012.2188912. |
[34] |
M. Zhu and S. Martínez,
On distributed convex optimization under inequality and equality constraints, IEEE Trans. Automat. Control, 57 (2012), 151-164.
doi: 10.1109/TAC.2011.2167817. |
show all references
References:
[1] |
N. S. Aybat and E. Y. Hamedani, Distributed primal-dual method for multi-agent sharing problem with conic constraints, 2016 50th Asilomar Conference on Signals, Systems and Computers, (2016), 777–782.
doi: 10.1109/ACSSC.2016.7869152. |
[2] |
N. S. Aybat and E. Y. Hamedani,
A distributed ADMM-like method for resource sharing over time-varying networks, SIAM J. Optim., 29 (2019), 3036-3068.
doi: 10.1137/17M1151973. |
[3] |
B. Baingana, G. Mateos and G. B. Giannakis,
Proximal-gradient algorithms for tracking cascades over social networks, IEEE Journal of Selected Topics in Signal Processing, 8 (2014), 563-575.
doi: 10.1109/JSTSP.2014.2317284. |
[4] |
A. Beck, A. Nedić, A. Ozdaglar and M. Teboulle,
An $O(1/k)$ gradient method for network resource allocation problems, IEEE Trans. Control Netw. Syst., 1 (2014), 64-73.
doi: 10.1109/TCNS.2014.2309751. |
[5] |
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
doi: 10.1017/CBO9780511804441.![]() ![]() |
[6] |
T.-H. Chang, A. Nedić and A. Scaglione,
Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Trans. Automat. Control, 59 (2014), 1524-1538.
doi: 10.1109/TAC.2014.2308612. |
[7] |
T.-H. Chang, M. Hong and X. Wang,
Multi-agent distributed optimization via inexact consensus ADMM, IEEE Trans. Signal Process., 63 (2015), 482-497.
doi: 10.1109/TSP.2014.2367458. |
[8] |
T.-H. Chang,
A proximal dual consensus ADMM method for multi-agent constrained optimization, IEEE Trans. Signal Process., 64 (2016), 3719-3734.
doi: 10.1109/TSP.2016.2544743. |
[9] |
J. C. Duchi, A. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Trans. Automat. Control, 57 (2012) 592–606.
doi: 10.1109/TAC.2011.2161027. |
[10] |
A. Falsone, K. Margellos, S. Garatti and M. Prandini,
Dual decomposition for multi-agent distributed optimization with coupling constraints, Automatica J. IFAC, 84 (2017), 149-158.
doi: 10.1016/j.automatica.2017.07.003. |
[11] |
X. S. Han, H. B. Gooi and D. S. Kirschen,
Dynamic economic dispatch: Feasible and optimal solutions, 2001 Power Engineering Society Summer Meeting. Conference Proceedings, 16 (2001), 22-28.
doi: 10.1109/PESS.2001.970332. |
[12] |
J. Li, C. Wu, Z. Wu and Q. Long,
Gradient-free method for nonsmooth distributed optimization, J. Global Optim., 61 (2015), 325-340.
doi: 10.1007/s10898-014-0174-2. |
[13] |
J. Li, G. Chen, Z. Dong and Z. Wu,
A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Comput. Optim. Appl., 64 (2016), 671-697.
doi: 10.1007/s10589-016-9826-0. |
[14] |
J. Li, C. Gu, Z. Wu and C. Wu, Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks, Complexity, 2017 (2017), Article ID 3610283, 10 pp.
doi: 10.1155/2017/3610283. |
[15] |
P. Di Lorenzo and G. Scutari,
NEXT: In-network nonconvex optimization, IEEE Trans. Signal Inform. Process. Netw., 2 (2016), 120-136.
doi: 10.1109/TSIPN.2016.2524588. |
[16] |
G. Mateos and G. B. Giannakis,
Distributed recursive least-squares: Stability and performance analysis, IEEE Trans. Signal Process., 60 (2012), 3740-3754.
doi: 10.1109/TSP.2012.2194290. |
[17] |
D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick and J. Lavaei, A survey of distributed optimization and control algorithms for electric power systems, IEEE Transactions on Smart Grid, 8 (2017), 2941-2962. Google Scholar |
[18] |
A. Nedić and A. Ozdaglar,
Distributed subgradient methods for multi-agent optimization, IEEE Trans. Automat. Control, 54 (2009), 48-61.
doi: 10.1109/TAC.2008.2009515. |
[19] |
A. Nedić and A. Olshevsky,
Distributed optimization over time-varying directed graphs, IEEE Trans. Automat. Control, 60 (2015), 601-615.
doi: 10.1109/TAC.2014.2364096. |
[20] |
A. Nedić, A. Olshevsky and W. Shi,
Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM J. Optim., 27 (2017), 2597-2633.
doi: 10.1137/16M1084316. |
[21] |
B. T. Polyak, Introduction to Optimization, Optimization Software, Inc., Publications Division, New York, 1987. |
[22] |
S. S. Ram, A. Nedić and V. V. Veeravalli,
Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory Appl., 147 (2010), 516-545.
doi: 10.1007/s10957-010-9737-7. |
[23] |
W. Shi, Q. Ling, K. Yuan, G. Wu and W. Yin,
On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Signal Process., 62 (2014), 1750-1761.
doi: 10.1109/TSP.2014.2304432. |
[24] |
W. Shi, Q. Ling, G. Wu and W. Yin,
EXTRA: An exact first-order algorithm for decentralized consensus optimization, SIAM J. Optim., 25 (2015), 944-966.
doi: 10.1137/14096668X. |
[25] |
K. I. Tsianos, S. Lawlor and M. G. Rabbat, Push-sum distributed dual averaging for convex optimization, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), (2012), 5453–5458.
doi: 10.1109/CDC.2012.6426375. |
[26] |
S. Wang and C. Li,
Distributed robust optimization in networked system, IEEE Transactions on Cybernetics, 47 (2017), 2321-2333.
doi: 10.1109/TCYB.2016.2613129. |
[27] |
X. Xia and A. M. Elaiw,
Optimal dynamic economic dispatch of generation: A review, Electric Power Systems Research, 80 (2010), 975-986.
doi: 10.1016/j.epsr.2009.12.012. |
[28] |
C. Yang, Y. Xu, L. Zhou and Y. Sun, Model-free composite control of flexible manipulators based on adaptive dynamic programming, Complexity, 2018 (2018), Article ID 9720309, 9 pp.
doi: 10.1155/2018/9720309. |
[29] |
D. Yuan, S. Xu and H. Zhao, Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41 (2011), 1715-1724. Google Scholar |
[30] |
D. Yuan, D. W. Ho and Y. Hong,
On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints, SIAM J. Control Optim., 54 (2016), 2872-2892.
doi: 10.1137/15M1048896. |
[31] |
D. Yuan, D. W. C. Ho and S. Xu,
Regularized primal-dual subgradient method for distributed constrained optimization, IEEE Transactions on Cybernetics, 46 (2016), 2109-2118.
doi: 10.1109/TCYB.2015.2464255. |
[32] |
Y. Zhang and G. B. Giannakis, Distributed stochastic market clearing with high-penetration wind power, IEEE Transactions on Power Systems, 31 (2016), 895-906. Google Scholar |
[33] |
Z. Zhang and M. Y. Chow,
Convergence analysis of the incremental cost consensus algorithm under different communication network topologies in a smart grid, IEEE Transactions on Power Systems, 27 (2012), 1761-1768.
doi: 10.1109/TPWRS.2012.2188912. |
[34] |
M. Zhu and S. Martínez,
On distributed convex optimization under inequality and equality constraints, IEEE Trans. Automat. Control, 57 (2012), 151-164.
doi: 10.1109/TAC.2011.2167817. |





Gen. | [ |
|||
1 | 0.0775795 | 20 | 0 | [0,575.88] |
2 | 0.01 | 40 | 0 | [0,100] |
3 | 0.25 | 20 | 0 | [0,140] |
6 | 0.01 | 40 | 0 | [0,100] |
8 | 0.0222222 | 20 | 0 | [0,550] |
9 | 0.01 | 40 | 0 | [0,100] |
12 | 0.0322581 | 20 | 0 | [0,410] |
Gen. | [ |
|||
1 | 0.0775795 | 20 | 0 | [0,575.88] |
2 | 0.01 | 40 | 0 | [0,100] |
3 | 0.25 | 20 | 0 | [0,140] |
6 | 0.01 | 40 | 0 | [0,100] |
8 | 0.0222222 | 20 | 0 | [0,550] |
9 | 0.01 | 40 | 0 | [0,100] |
12 | 0.0322581 | 20 | 0 | [0,410] |
Number of node |
Alg. DDSG-PS | Alg. DDSG |
10 | 38 | 34 |
50 | 97 | 99 |
100 | 203 | 201 |
Number of node |
Alg. DDSG-PS | Alg. DDSG |
10 | 38 | 34 |
50 | 97 | 99 |
100 | 203 | 201 |
Dimension of |
Alg. DDSG-PS | Alg. DDSG |
3 | 50 | 84 |
5 | 77 | 98 |
9 | 108 | 136 |
Dimension of |
Alg. DDSG-PS | Alg. DDSG |
3 | 50 | 84 |
5 | 77 | 98 |
9 | 108 | 136 |
[1] |
Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2021002 |
[2] |
Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 |
[3] |
Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021005 |
[4] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021013 |
[5] |
Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009 |
[6] |
Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020364 |
[7] |
Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021001 |
[8] |
Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111 |
[9] |
Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295 |
[10] |
Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325 |
[11] |
Yujuan Li, Huaifu Wang, Peipei Zhou, Guoshuang Zhang. Some properties of the cycle decomposition of WG-NLFSR. Advances in Mathematics of Communications, 2021, 15 (1) : 155-165. doi: 10.3934/amc.2020050 |
[12] |
Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033 |
[13] |
Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011 |
[14] |
Xi Zhao, Teng Niu. Impacts of horizontal mergers on dual-channel supply chain. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020173 |
[15] |
Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285 |
[16] |
Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020321 |
[17] |
Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020055 |
[18] |
Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305 |
[19] |
Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65 |
[20] |
Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]