A Continuous-Time Distributed Algorithm for Solving a Class of Decomposable Nonconvex Quadratic Programming

Zhao, Yan; Liu, Qingshan

doi:10.1515/jaiscr-2018-0018

Abstract

In this paper, a continuous-time distributed algorithm is presented to solve a class of decomposable quadratic programming problems. In the quadratic programming, even if the objective function is nonconvex, the algorithm can still perform well under an extra condition combining with the objective, constraint and coupling matrices. Inspired by recent advances in distributed optimization, the proposed continuous-time algorithm described by multi-agent network with consensus is designed and analyzed. In the network, each agent only accesses the local information of its own and from its neighbors, then all the agents in a connected network cooperatively find the optimal solution with consensus.

References

[1] R. H. Byrd, M. E. Hribar, and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM Journal on Optimization, vol. 9, no. 4, pp. 877-900, 1999.10.1137/S1052623497325107
Search in Google Scholar Back to article
[2] M. A. Figueiredo, R. D. Nowak, and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 4, pp. 586-597, Dec. 2007.10.1109/JSTSP.2007.910281
Search in Google Scholar Back to article
[3] J. Hopfield and D. Tank, Computing with neural circuits: A model, Science, vol. 233, no. 4764, pp. 625-633, 1986.
Search in Google Scholar Back to article
[4] Y. Xia, G. Feng, and J. Wang, A novel recurrent neural network for solving nonlinear optimization problems with inequality constraints, IEEE Transactions on Neural Networks, vol. 19, no. 8, pp. 1340-1353, Aug. 2008.
Search in Google Scholar Back to article
[5] Q. Liu and J. Wang, L1-minimization algorithms for sparse signal reconstruction based on a projection neural network, IEEE Transactions on Neural Networks and Learning Systems, vol. 27, no. 3, pp. 698-707, Mar. 2016.10.1109/TNNLS.2015.248100626513806
Search in Google Scholar Back to article
[6] Q. Liu and J. Wang, A projection neural network for constrained quadratic minimax optimization, IEEE Transactions on Neural Networks and Learning Systems, vol. 26, no. 11, pp. 2891-2900, Nov. 2015.
Search in Google Scholar Back to article
[7] G. Tambouratzis, Using particle swarm optimization to accurately identify syntactic phrases in free text, Journal of Artificial Intelligence & Soft Computing Research, vol. 8, no. 1, pp. 63-67, 2018.10.1515/jaiscr-2018-0004
Search in Google Scholar Back to article
[8] S. Sadiqbatcha, J. Saeed, and A. Yiannis, Particle swarm optimization for solving a class of type-1 and type-2 fuzzy nonlinear equations, Journal of Artificial Intelligence & Soft Computing Research, vol. 8, no. 2, pp. 103-110, 2018.10.1515/jaiscr-2018-0007
Search in Google Scholar Back to article
[9] C. Rotar and L. B. Iantovics, Directed evolution - a new metaheuristc for optimization, Journal of Artificial Intelligence & Soft Computing Research, vol. 7, no. 3, pp. 183-200, 2017.10.1515/jaiscr-2017-0013
Search in Google Scholar Back to article
[10] J. Antonio, G. Huang, and W. Tsai, A fast distributed shortest path algorithm for a class of hierarchically clustered data networks, IEEE Transactions on Computers, pp. 710-724, 1992.10.1109/12.144623
Search in Google Scholar Back to article
[11] S. Sundhar Ram, A. Nedić, and V. V. Veeravalli, A new class of distributed optimization algorithms: Application to regression of distributed data, Optimization Methods and Software, vol. 27, no. 1, pp. 71-88, 2012.10.1080/10556788.2010.511669
Search in Google Scholar Back to article
[12] L. Xiao, S. Boyd, and S.-J. Kim, Distributed average consensus with least-mean-square deviation, Journal of Parallel and Distributed Computing, vol. 67, no. 1, pp. 33-46, 2007.10.1016/j.jpdc.2006.08.010
Search in Google Scholar Back to article
[13] A. Nedic, A. Ozdaglar, and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, vol. 55, no. 4, pp. 922-938, Apr. 2010.10.1109/TAC.2010.2041686
Search in Google Scholar Back to article
[14] M. Zhu and S. Martínez, On distributed convex optimization under inequality and equality constraints, IEEE Transactions on Automatic Control, vol. 57, no. 1, pp. 151-164, Jan. 2012.10.1109/TAC.2011.2167817
Search in Google Scholar Back to article
[15] D. Yuan, S. Xu, and H. Zhao, Distributed primaldual subgradient method for multiagent optimization via consensus algorithms, IEEE Transactions on Systems, Man and Cybernetics - Part B: Cybernetics, vol. 41, no. 6, pp. 1715-1724, Dec. 2011.10.1109/TSMCB.2011.216039421824853
Open DOI Search in Google Scholar Back to article
[16] B. Gharesifard and J. Cortés, Distributed continuous-time convex optimization on weightbalanced digraphs, IEEE Transactions on Automatic Control, vol. 59, no. 3, pp. 781-786, Mar. 2014.10.1109/TAC.2013.2278132
Search in Google Scholar Back to article
[17] Q. Liu and J. Wang, A second-order multi-agent network for bound-constrained distributed optimization, IEEE Transactions on Automatic Control, vol. 60, no. 12, pp. 3310-3315, Dec. 2015.
Search in Google Scholar Back to article
[18] M. Rabbat and R. Nowak, Distributed optimization in sensor networks, in Proc. 3rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA, Apr. 2004, pp. 20-27.10.1145/984622.984626
Search in Google Scholar Back to article
[19] J. F. Mota, J. M. Xavier, P. M. Aguiar, and M. Püschel, Distributed optimization with local domains: Applications in MPC and network flows, IEEE Transactions on Automatic Control, vol. 60, no. 7, pp. 2004-2009, July 2015.
Search in Google Scholar Back to article
[20] W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control. Springer- Verlag London Limited, 2008.10.1007/978-1-84800-015-5
Search in Google Scholar Back to article
[21] A. Nedić and A. Ozdaglar, Subgradient methods for saddle-point problems, Journal of optimization theory and applications, vol. 142, no. 1, pp. 205- 228, 2009.10.1007/s10957-009-9522-7
Search in Google Scholar Back to article
[22] I. Lobel, A. Ozdaglar, and D. Feijer, Distributed multi-agent optimization with state-dependent communication, Mathematical Programming, vol. 129, no. 2, pp. 255-284, 2011.10.1007/s10107-011-0467-x
Search in Google Scholar Back to article
[23] P. Lin, W. Ren, and Y. Song, Distributed multiagent optimization subject to nonidentical constraints and communication delays, Automatica, vol. 65, pp. 120-131, 2016.10.1016/j.automatica.2015.11.014
Search in Google Scholar Back to article
[24] M. Bürger, G. Notarstefano, and F. Allgöwer, A polyhedral approximation framework for convex and robust distributed optimization, IEEE Transactions on Automatic Control, vol. 59, no. 2, pp. 384-395, Feb. 2014.10.1109/TAC.2013.2281883
Search in Google Scholar Back to article
[25] L. Carlone, V. Srivastava, F. Bullo, and G. C. Calafiore, Distributed random convex programming via constraints consensus, SIAM Journal on Control and Optimization, vol. 52, no. 1, pp. 629- 662, 2014.10.1137/120885796
Search in Google Scholar Back to article
[26] X.Wang, Y. Hong, and H. Ji, Distributed optimization for a class of nonlinear multiagent systems with disturbance rejection, IEEE Transactions on Cybernetics, vol. 46, no. 7, pp. 1655-1666, July 2016.10.1109/TCYB.2015.245316726316285
Open DOI Search in Google Scholar Back to article
[27] S. Yang, Q. Liu, and J.Wang, Distributed optimization based on a multiagent system in the presence of communication delays, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 5, pp. 717-728, May 2017.10.1109/TSMC.2016.2531649
Search in Google Scholar Back to article
[28] H. Wang, X. Liao, T. Huang, and C. Li, Cooperative distributed optimization in multiagent networks with delays, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 45, no. 2, pp. 363-369, Feb. 2015.10.1109/TSMC.2014.2332306
Search in Google Scholar Back to article
[29] Q. Liu, S. Yang, and J. Wang, A collective neurodynamic approach to distributed constrained optimization, IEEE Transactions on Neural Networks and Learning Systems, vol. 28, no. 8, pp. 1747- 1758, Aug. 2017.
Search in Google Scholar Back to article
[30] M. Bazaraa, H. Sherali, and C. Shetty, Nonlinear Programming: Theory and Algorithms (3rd Ed.) Hoboken, New Jersey: John Wiley & Sons, 2006.
Search in Google Scholar Back to article
[31] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, New York: Academic, 1982.
Search in Google Scholar Back to article
[32] Q. Liu and K. Li, A continuous-time algorithm based on multi-agent system for distributed least absolute deviation subject to hybrid constraints,” in Proc. 43rd Annual Conference of the IEEE Industrial Electronics Society, 2017, pp. 7381-7386.10.1109/IECON.2017.8217293
Search in Google Scholar Back to article
[33] J. LaSalle, The Stability of Dynamical Systems Philadelphia, PA, USA: SIAM, 1976.10.21236/ADA031020
Search in Google Scholar Back to article

A Continuous-Time Distributed Algorithm for Solving a Class of Decomposable Nonconvex Quadratic Programming

Abstract

Paradigm

My account