Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Jueyou Li

    * Corresponding author: Jueyou Li

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

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The directed connected graph at time $ t $ with $ \mathscr{G}[t] = (\mathscr{V}, \mathscr{E}[t]) $

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

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

    Figure 4.  Total generation v.s. demand

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

    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
  • [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. BainganaG. 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. BeckA. 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. VandenbergheConvex Optimization, Cambridge University Press, Cambridge, 2004.  doi: 10.1017/CBO9780511804441.
    [6] T.-H. ChangA. 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. ChangM. 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. FalsoneK. MargellosS. 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. HanH. 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. LiC. WuZ. 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. LiG. ChenZ. 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. MolzahnF. DörflerH. SandbergS. H. LowS. ChakrabartiR. 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. RamA. 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. ShiQ. LingK. YuanG. 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. ShiQ. LingG. 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. YuanS. 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. YuanD. 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. YuanD. 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.
  • 加载中




Article Metrics

HTML views(1118) PDF downloads(514) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint