
-
Previous Article
Optimal reinsurance and investment strategies for an insurer and a reinsurer under Hestons SV model: HARA utility and Legendre transform
- JIMO Home
- This Issue
-
Next Article
Effect of institutional deleveraging on option valuation problems
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] |
Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066 |
[2] |
Ru Li, Guolin Yu. Strict efficiency of a multi-product supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2203-2215. doi: 10.3934/jimo.2020065 |
[3] |
Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 |
[4] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
[5] |
Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021051 |
[6] |
Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. |
[7] |
Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, 2021, 15 (3) : 397-413. doi: 10.3934/amc.2020073 |
[8] |
Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849 |
[9] |
Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006 |
[10] |
Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109 |
[11] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[12] |
Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361 |
[13] |
Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021009 |
[14] |
Mrinal K. Ghosh, Somnath Pradhan. A nonzero-sum risk-sensitive stochastic differential game in the orthant. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021025 |
[15] |
Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077 |
[16] |
Jinsen Guo, Yongwu Zhou, Baixun Li. The optimal pricing and service strategies of a dual-channel retailer under free riding. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021056 |
[17] |
Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercion-resistant blockchain-based E-voting protocol with receipts. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021005 |
[18] |
Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228 |
[19] |
Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 |
[20] |
Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021013 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]