Distributed Subgradient Algorithm for Multi-agent Convex Optimization with Local Constraint Sets
Applied and Computational Mathematics
Volume 5, Issue 3, June 2016, Pages: 150-159
Received: Jun. 12, 2016;
Accepted: Jun. 20, 2016;
Published: Jul. 13, 2016
Views 3263 Downloads 107
Qingguo Lü, College of Electronic and Information Engineering, Southwest University, Chongqing, PR China
Huaqing Li, College of Electronic and Information Engineering, Southwest University, Chongqing, PR China; State Key Laboratory of Power Transmission Equipment & System Security and New Technology, Chongqing University, Chongqing, PR China
Li Xiao, Department of Mathematics and Information Engineering, Chongqing University of Education, Chongqing, PR China
This paper considers a distributed constrained optimization problem, where the objective function is the sum of local objective functions of distributed nodes in a network. The estimate of each agent is restricted to different convex sets. To solve this optimization problem which is not necessarily smooth, we study a novel distributed projected subgradient algorithm for multi-agent optimization with nonidentical constraint sets and switching topologies. The algorithm shows that each agent minimizes its own objective function while communicating information locally with other agents over a network with time-varying topologies but satisfying a standard connectivity property. Under the assumption that the network topology is weight-balanced, the novel distributed subgradient algorithm we proposed is proven to be convergent. Particularly, we suppose the step-size is various, which is different from previous work on multi-agent optimization that makes worst-case assumption with constant step-size.
Distributed Subgradient Algorithm for Multi-agent Convex Optimization with Local Constraint Sets, Applied and Computational Mathematics.
Vol. 5, No. 3,
2016, pp. 150-159.
A. Nedić and A. Ozdaglar. “Distributed subgradient methods for multiagent optimization”, IEEE Transactions on Automatic Control, 54 (1): 48-61, 2009.
B. Gu, V. S. Sheng, K. Y. Tay, et al. “Incremental support vector learning for ordinal regression,” IEEE Transactions on Neural Networks and Learning Systems, vol. 26, no. 7, pp. 1403-1416, 2015.
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.
H. Li, X. Liao, X. Lei, et al. Second-order consensus seeking in multi-agent systems with nonlinear dynamics over random switching directed networks. IEEE Transactions on Circuits and Systems I: Regular Papers, 2013, 60 (6): 1595-1607.
B. Gu, V. S. Sheng, Z. Wang, D. Ho, S. Osman, and S. Li, “Incremental learning for ν-Support Vector Regression,” Neural Networks, vol. 67, pp. 140-150, 2015.
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.
P. Bianchi, J. Jakubowicz, Convergence of a multi-agent projected stochastic gradient algorithm for non-convex optimization, IEEE Transactions on Automatic Control, 2013, 58 (2): 391–405.
Z. Xia, X. Wang, X. Sun, and Q. Wang, “A Secure and dynamic multi-keyword ranked search scheme over encrypted cloud data,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 2, pp. 340-352, 2015.
I. Necoara, Random coordinate descent algorithms for multi-agent convex optimization over networks, IEEE Transactions on Automatic Control, 2013, 58 (8): 2001-2012.
Y. Lou, G. Shi, K. H. Johansson, Y. Hong, Approximate projected consensus for convex intersection computation: Convergence analysis and critical error angle, IEEE Transactions on Automatic Control, 2014, 59 (7): 1722-1736.
Z. Fu, X. Sun, Q. Liu, L. Zhou, and J. Shu, “Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing,” IEICE Transactions on Communications, vol. E98-B, no. 1, pp. 190-200, 2015.
Z. J. Towfic, A. H. Sayed, Adaptive penalty-based distributed stochastic convex optimization, IEEE Transactions on Signal Process, 2014, 62 (15) 3924-3938.
H. Li, X. Liao, T. Huang, et al. Second-order global consensus in multi-agent networks with random directional link failure. IEEE Transactions on Neural Networks and Learning Systems, 2015, 26 (3): 565-575.
B. Chen, H. Shu, G. Coatrieux, G. Chen, et al. “Color image analysis by quaternion-type moments,” Journal of Mathematical Imaging and Vision, vol. 51, no. 1, pp. 124-144, 2015.
A. H. Sayed, Adaptation, learning, and optimization over networks, in: Foundations and Trends in Machine Learning, Vol. 7, NOW Publishers, Boston-Delft, 2014, pp. 4-5.
H. Li, G. Chen, T. Huang, et al. High-performance consensus control in networked systems with limited bandwidth communication and time-varying directed topologies. IEEE Transactions on Neural Networks and Learning Systems, 2016, DOI: 10.1109/TNNLS.2016.2519894.
X. Wen, L. Shao, Y. Xue, and W. Fang, “A rapid learning algorithm for vehicle classification,” Information Sciences, vol. 295, no. 1, pp. 395-406, 2015.
B. Johansson, P. Soldati, and M. Johansson, “Mathematical decomposition techniques for distributed cross-layer optimization of data networks,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1535-1547, Aug. 2006.
M. Rabbat, R. Nowak, and J. Bucklew, “Generalized consensus computation in networked systems with erasure links,” in IEEE SPAWC, 2005.
Y. Zheng, B. Jeon, D. Xu, Q. M. Jonathan Wu, and H. Zhang, “Image segmentation by generalized hierarchical fuzzy C-means algorithm,” Journal of Intelligent and Fuzzy Systems, vol. 28, no. 2, pp. 961-973, 2015.
H. Li, X. Liao, G. Chen, et al. Event-triggered asynchronous intermittent communication strategy for synchronization in complex dynamical networks. Neural Networks, 2015, 66: 1-10.
M. Zhu and S. Martinez, “On distributed convex optimization under inequality and equality constraints,” IEEE Transactions on Automatic Control, 2012, vol. 57, no. 1, pp. 151-164.
M. Zhu and S. Martinez, “An approximate dual subgradient algorithm for multi-agent non-convex optimization,” IEEE Transactions on Automatic Control, 2013, vol. 58, no. 6, pp. 1534-1539.
Z. Xia, X. Wang, X. Sun, and B. Wang, “Steganalysis of least significant bit matching using multi-order differences,” Security and Communication Networks, vol. 7, no. 8, pp. 1283-1291, 2014.
D. Yuan, S. Xu, and H. Zhao, “Distributed primal–dual subgradient method for multiagent optimization via consensus algorithms,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 41, no. 6, pp. 1715-1724, Dec. 2011.
B. Gu, X. Sun, and V. S. Sheng, “Structural minimax probability machine,” IEEE Transactions on Neural Networks and Learning Systems, DOI: 10.1109/TNNLS.2016.2544779, 2016.
T. H. Chang, A. Nedic, and A. Scaglione, “Distributed constrained optimization by consensus-based primal–dual perturbation method,” IEEE Transactions on Automatic Control, 2014, vol. 59, no. 6, pp. 1524-1538.
H. Li, X. Liao, T. Huang. Second-order locally dynamical consensus of multi-agent systems with arbitrarily fast switching directed topologies. IEEE Transactions on Systems Man and Cybernetics: Systems, 2013, 43 (6): 1343-1353.
C. Godsil and G. Royle, Algebraic Graph Theory, New York: Springer-Verlag, 2001.
M. Zhu, and S. Martínez. Discrete-time dynamic average consensus, Automatica, 2010, 46 (2): 322-329.
H. Li, G. Chen, T. Huang, et al. Event-triggering sampling based leader-following consensus in second-order multi-agent systems. IEEE Transactions on Automatic Control, 2015, 60 (7): 1998-2003.
B. Johansson, A. Speranzon, M. Johansson, and K. H. Johansson, “On decentralized negotiation of optimal consensus,” Automatical, pp. 1175-1179, Jul. 2008.
H. Li, G. Chen, X. Liao, et al. Quantized data-based leader-following consensus of general discrete-time multi-agent systems, IEEE Transactions on Circuits and Systems II：Express Briefs, 2016, 63 (4): 401-405.
Ren W, Beard R W. Distributed consensus in multi-vehicle cooperative control. Springer-Verlag, London, 2008.
H. Li, G. Chen, T. Huang, et al. Event-triggered distributed consensus over directed digital detworks with limited bandwidth, IEEE Transactions on Cybernetics, DOI: 10.1109/TCYB.2015.2496977.
J. Shen, H. Tan, J. Wang, J. Wang, and S. Lee, “A novel routing protocol providing good transmission reliability in underwater sensor networks,” Journal of Internet Technology, vol. 16, no. 1, pp. 171-178, 2015.