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

Li Xiao; Junjie Bao; Xi Shi

doi:doi:10.11648/j.acm.20160505.15

| Peer-Reviewed

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

Li Xiao, Junjie Bao, Xi Shi

Published in Applied and Computational Mathematics (Volume 5, Issue 5)

Received: 7 August 2016 Accepted: 5 October 2016 Published: 27 October 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Li Xiao

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

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

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

Download PDF

Sections

Plain Text BibTeX RIS

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