| Peer-Reviewed

Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints

Received: 7 August 2016     Accepted: 5 October 2016     Published: 27 October 2016
Views:       Downloads:
Abstract

In this paper, we present an improved subgradient algorithm for solving a general multi-agent convex optimization problem in a distributed way, where the agents are to jointly minimize a global objective function subject to a global inequality constraint, a global equality constraint and a global constraint set. The global objective function is a combination of local agent objective functions and the global constraint set is the intersection of each agent local constraint set. Our motivation comes from networking applications where dual and primal-dual subgradient methods have attracted much attention in the design of decentralized network protocols. Our main focus is on constrained problems where the local constraint sets are identical. Thus, we propose a distributed primal-dual subgradient algorithm, which is based on the description of the primal-dual optimal solutions as the saddle points of the penalty functions. We show that, the algorithm can be implemented over networks with changing topologies but satisfying a standard connectivity property, and allow the agents to asymptotically converge to optimal solution with optimal value of the optimization problem under the Slater’s condition.

Published in Applied and Computational Mathematics (Volume 5, Issue 5)
DOI 10.11648/j.acm.20160505.15
Page(s) 213-229
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

Consensus, Saddle Point, Distributed Optimization, Subgradient Algorithm

References
[1] J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: convergence analysis and network scaling, IEEE Transactions on Automatic control, 2012, 57(3): 592-606.
[2] A. Nedić, A. Ozdaglar, and P. Parrilo. Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 2010, 55(4): 922-938.
[3] K. Srivastava and A. Nedić. Distributed asynchronous constrained stochastic optimization, IEEE Journal of Selected Topics in Signal Processing, 2011, 5(4): 772-790.
[4] S. S. Ram, A. Nedić and V. V. Veeravalli, “Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization,” Journal of optimization theory and applications, 2010, 147(3): 516-545
[5] S. S. Ram, A. Nedić, and V. V. Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization, Journal of optimization theory and applications, 2010, 147(3): 516-545.
[6] A. Nedić and A. Ozdaglar. “Distributed Subgradient Methods for Multiagent Optimization”, IEEE Transactions on Automatic Control, 54(1): 48-61, 2009.
[7] S. S. Ram, A. Nedić, and V. V. Veeravalli. Incremental stochastic subgradient algorithms for convex optimization, SIAM Journal on Optimization, 2009, 20(2): 691-717.
[8] J. Lu, C. Y. Tang, P. R. Regier, and et al. A gossip algorithm for convex consensus optimization over networks, American Control Conference (ACC), 2010. IEEE, 2010: 301-308.
[9] M. Zhu and S. Martínez. “An approximate dual subgradient algorithm for distributed non-convex constrained optimization”, in the proc. of Conference on Decision and Control, 2010, pp. 7487-7492.
[10] M. Rabi and M. Johansson. A simple peer-to-peer algorithm for distributed optimization in sensor networks, IEEE Conference on Decision and Control. 2007, 46: 4705-4710.
[11] E. Wei, A. Ozdaglar, and A. Jadbabaie. A distributed newton method for network utility maximization, IEEE Conference on Decision and Control (CDC). 2010, 49th: 1816-1821.
[12] A. Nedić. Asynchronous broadcast-based convex optimization over a network, IEEE Transactions on Automatic Control, 2011, 56(6): 1337-1351.
[13] A. Nedić, A. Ozdaglar, and P. Parrilo. Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 2010, 55(4): 922-938.
[14] M. Zhu and S. Martínez. On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods, arXiv preprint arXiv:1001.2612, 2010.
[15] B. Johansson, T. Keviczky, M. Johansson, and K. H. Johansson. Subgradient methods and consensus algorithms for solving convex optimization problems, In IEEE Conference on Decision and Control, pages 4185-4190, Cancun, Mexico, December 2008.
[16] A. Nedić, A. Olshevsky, A. Ozdaglar, and et al. Distributed subgradient methods and quantization effects, IEEE Conference on Decision and Control. 2008: 4177-4184.
[17] A. Nedić and A. Ozdaglar. Subgradient methods for saddle-point problems, Journal of optimization theory and applications, 2009, 142(1): 205-228.
[18] A. Nedić and A. Ozdaglar. Approximate primal solutions and rate analysis for dual subgradient methods, SIAM Journal on Optimization, 2009, 19(4): 1757-1780.
[19] D. P. Bertsekas. Convex optimization theory, Athena Scientific, 2009.
[20] D. P. Bertsekas, A. Nedić, and A. Ozdaglar. Convex analysis and optimization, Athena Scientific, 2003.
[21] M. Zhu, and S. Martínez. Discrete-time dynamic average consensus, Automatica, 2010, 46(2): 322-329.
[22] A. Nedić and A. Ozdaglar. Subgradient methods in network resource allocation: Rate analysis, Information Sciences and Systems, IEEE Conference on Decision and Control, 2008: 1189-1194.
Cite This Article
  • APA Style

    Li Xiao, Junjie Bao, Xi Shi. (2016). Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints. Applied and Computational Mathematics, 5(5), 213-229. https://doi.org/10.11648/j.acm.20160505.15

    Copy | Download

    ACS Style

    Li Xiao; Junjie Bao; Xi Shi. Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints. Appl. Comput. Math. 2016, 5(5), 213-229. doi: 10.11648/j.acm.20160505.15

    Copy | Download

    AMA Style

    Li Xiao, Junjie Bao, Xi Shi. Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints. Appl Comput Math. 2016;5(5):213-229. doi: 10.11648/j.acm.20160505.15

    Copy | Download

  • @article{10.11648/j.acm.20160505.15,
      author = {Li Xiao and Junjie Bao and Xi Shi},
      title = {Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints},
      journal = {Applied and Computational Mathematics},
      volume = {5},
      number = {5},
      pages = {213-229},
      doi = {10.11648/j.acm.20160505.15},
      url = {https://doi.org/10.11648/j.acm.20160505.15},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20160505.15},
      abstract = {In this paper, we present an improved subgradient algorithm for solving a general multi-agent convex optimization problem in a distributed way, where the agents are to jointly minimize a global objective function subject to a global inequality constraint, a global equality constraint and a global constraint set. The global objective function is a combination of local agent objective functions and the global constraint set is the intersection of each agent local constraint set. Our motivation comes from networking applications where dual and primal-dual subgradient methods have attracted much attention in the design of decentralized network protocols. Our main focus is on constrained problems where the local constraint sets are identical. Thus, we propose a distributed primal-dual subgradient algorithm, which is based on the description of the primal-dual optimal solutions as the saddle points of the penalty functions. We show that, the algorithm can be implemented over networks with changing topologies but satisfying a standard connectivity property, and allow the agents to asymptotically converge to optimal solution with optimal value of the optimization problem under the Slater’s condition.},
     year = {2016}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints
    AU  - Li Xiao
    AU  - Junjie Bao
    AU  - Xi Shi
    Y1  - 2016/10/27
    PY  - 2016
    N1  - https://doi.org/10.11648/j.acm.20160505.15
    DO  - 10.11648/j.acm.20160505.15
    T2  - Applied and Computational Mathematics
    JF  - Applied and Computational Mathematics
    JO  - Applied and Computational Mathematics
    SP  - 213
    EP  - 229
    PB  - Science Publishing Group
    SN  - 2328-5613
    UR  - https://doi.org/10.11648/j.acm.20160505.15
    AB  - In this paper, we present an improved subgradient algorithm for solving a general multi-agent convex optimization problem in a distributed way, where the agents are to jointly minimize a global objective function subject to a global inequality constraint, a global equality constraint and a global constraint set. The global objective function is a combination of local agent objective functions and the global constraint set is the intersection of each agent local constraint set. Our motivation comes from networking applications where dual and primal-dual subgradient methods have attracted much attention in the design of decentralized network protocols. Our main focus is on constrained problems where the local constraint sets are identical. Thus, we propose a distributed primal-dual subgradient algorithm, which is based on the description of the primal-dual optimal solutions as the saddle points of the penalty functions. We show that, the algorithm can be implemented over networks with changing topologies but satisfying a standard connectivity property, and allow the agents to asymptotically converge to optimal solution with optimal value of the optimization problem under the Slater’s condition.
    VL  - 5
    IS  - 5
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics and Information Engineering, Chongqing University of Education, Chongqing, PR China

  • Department of Mathematics and Information Engineering, Chongqing University of Education, Chongqing, PR China

  • Department of Mathematics and Information Engineering, Chongqing University of Education, Chongqing, PR China

  • Sections