Distributed convex optimization with coupling constraints over time-varying directed graphs†

Bingru Zhang; Chuanye Gu; Jueyou Li

doi:10.3934/jimo.2020061

Article Contents

2021, Volume 17, Issue 4: 2119-2138. Doi: 10.3934/jimo.2020061

This issue Previous Article Effect of institutional deleveraging on option valuation problems Next Article Optimal reinsurance and investment strategies for an insurer and a reinsurer under Hestons SV model: HARA utility and Legendre transform

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

^* Corresponding author: Jueyou Li
^* Corresponding author: Jueyou Li

Received: February 28, 2019

Revised: October 31, 2019

Early access: March 2020

Published: July 2021

^† This research was partially supported by the NSFC 11971083 and 11871128, by the Natural Science Foundation Projection of Chongqing cstc2017jcyjAX0253, by the Fund Program of Chongqing Social Science Planning of China 2017YBGL137 and by the Science and Technology Research Program of Chongqing Municipal Education Commission KJQN201800520.

Abstract Full Text(HTML) Figure(5) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 47N10; Secondary: 68W15.

Citation:

FullText(HTML)

Figure 1. The directed connected graph at time $ t $ with $ \mathscr{G}[t] = (\mathscr{V}, \mathscr{E}[t]) $

Download: Full-size image PowerPoint slide

Figure 2. Dual variables (fanxiexian_myfh/MWh) v.s. iterations

Download: Full-size image PowerPoint slide

Figure 3. Generation outputs (MW) v.s. iterations

Download: Full-size image PowerPoint slide

Figure 4. Total generation v.s. demand

Download: Full-size image PowerPoint slide

Figure 5. Value of total cost function v.s. iterations

Download: Full-size image PowerPoint slide

Table 1. Parameters for 7 generators in IEEE 57-bus system

Gen.	$ a_{i} $	$ b_{i} $	$ c_{i} $	[$ p_{i}^{\mathrm{min}},p_{i}^{\mathrm{max}} $]
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]

| Show Table

DownLoad: CSV

Table 2. Number of iterations with different nodes for both Algorithms DDSG-PS and DDP

Number of node $ m $	Alg. DDSG-PS	Alg. DDSG
10	38	34
50	97	99
100	203	201

| Show Table

DownLoad: CSV

Table 3. Number of iterations with different dimensions for both Algorithms DDSG-PS and DDP

Dimension of $ \widehat{\mathbf{x}}_{i} $	Alg. DDSG-PS	Alg. DDSG
3	50	84
5	77	98
9	108	136

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.