Archive




Volume 5, Issue 5, October 2016, Page: 213-229
Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints
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
Received: Aug. 7, 2016;       Accepted: Oct. 5, 2016;       Published: Oct. 27, 2016
DOI: 10.11648/j.acm.20160505.15      View  2762      Downloads  163
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.
Keywords
Consensus, Saddle Point, Distributed Optimization, Subgradient Algorithm
To cite this article
Li Xiao, Junjie Bao, Xi Shi, Distributed Subgradient Algorithm for Multi-Agent Convex Optimization with Global Inequality and Equality Constraints, Applied and Computational Mathematics. Vol. 5, No. 5, 2016, pp. 213-229. doi: 10.11648/j.acm.20160505.15
Copyright
Copyright © 2016 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Reference
[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.
Browse journals by subject