×

Distributed continuous-time approximate projection protocols for shortest distance optimization problems. (English) Zbl 1338.93026

Summary: In this paper, we investigate a distributed shortest distance optimization problem for a multi-agent network to cooperatively minimize the sum of the quadratic distances from some convex sets, where each set is only associated with one agent. To deal with this optimization problem with projection uncertainties, we propose a distributed continuous-time dynamical protocol, where each agent can only obtain an approximate projection and communicate with its neighbors over a time-varying communication graph. First, we show that no matter how large the approximate angle is, system states are always bounded for any initial condition, and uniformly bounded with respect to all initial conditions if the inferior limit of the stepsize is greater than zero. Then, in both cases of nonempty and empty intersection of convex sets, we provide stepsize and approximate angle conditions to ensure the optimal convergence, respectively. Moreover, we also give some characterizations about the optimal solutions for the empty intersection case.

MSC:

93A14 Decentralized systems
68T42 Agent technology and artificial intelligence
49N90 Applications of optimal control and differential games
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aubin, J.; Cellina, A., Differential inclusions, (1984), Springer-Verlag Berlin
[2] Bertsekas, D. P.; Tsitsiklis, J., Parallel and distributed computation: numerical methods, (1989), Princeton Hall Englewood Cliffs, NJ · Zbl 0743.65107
[3] Danskin, J., The theory of MAX-MIN, with applications, SIAM Journal on Applied Mathematics, 14, 4, 641-664, (1966) · Zbl 0144.43301
[4] Deutsch, F., Rate of convergence of the method of alternating projections, (Brosowski, B.; Deutsch, F., Parametric optim. approx., Vol. 76, (1983), Birkhäuser Basel, Switzerland), 96-107
[5] do Carmo, M., Differential geometry of curves and surfaces, (1976), Prentice-Hall Englewood Cliffs, NJ · Zbl 0326.53001
[6] Droge, G.; Kawashima, H.; Egerstedt, M., Continuous-time proportional-integral distributed optimization for networked systems, Journal of Decision and Control, 1, 3, 191-213, (2014)
[7] Francis, R. L.; McGinnis, L. F.; White, J. A., Facility layout and location: an analytical approach, (1992), Prentice Hall Englewood Cliffs, NJ
[8] Gharesifard, B.; Cortés, J., Distributed convergence to Nash equilibria in two-network zero-sum games, Automatica, 49, 6, 1683-1692, (2013) · Zbl 1360.91012
[9] Gharesifard, B.; Cortés, J., Distributed continuous-time convex optimization on weight-balanced digraphs, IEEE Transactions on Automatic Control, 59, 3, 781-786, (2014) · Zbl 1360.90257
[10] Godsil, C.; Royle, G., Algebraic graph theory, (2001), Springer-Verlag New York · Zbl 0968.05002
[11] Gubin, L.; Polyak, B.; Raik, E., The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics, 7, 6, 1211-1228, (1967)
[12] Jakovetic, D.; Xavier, J.; Moura, J. M.F., Cooperative convex optimization in networked systems: augmented Lagrangian algorithms with directed gossip communication, IEEE Transactions on Signal Processing, 59, 8, 3889-3902, (2011) · Zbl 1392.94018
[13] Johansson, B.; Rabi, M.; Johansson, M., A randomized incremental subgradient method for distributed optimization in networked systems, SIAM Journal on Optimization, 20, 3, 1157-1170, (2009) · Zbl 1201.65100
[14] Kvaternik, K., & Pavel, L. (2012). A continuous-time decentralized optimization scheme with positivity constraints. In 51st IEEE conference on decision and control (pp. 6801-6807).
[15] Lin, P., & Ren, W. (2012). Distributed shortest distance consensus problem in multi-agent systems. In 51st IEEE conference on decision and control, 2012 (pp. 4696-4701).
[16] Lou, Y.; Shi, G.; Johansson, K. H.; Hong, Y., Convergence of random sleep algorithms for optimal consensus, Systems & Control Letters, 62, 12, 1196-1202, (2013) · Zbl 1282.93019
[17] Lou, Y.; Shi, G.; Johansson, K. H.; Hong, Y., Approximate projected consensus for convex intersection computation: convergence analysis and critical error angle, IEEE Transactions on Automatic Control, 59, 7, 1722-1736, (2014) · Zbl 1360.90204
[18] Lu, J.; Tang, C. Y., Zero-gradient-sum algorithms for distributed convex optimization: the continuous-time case, IEEE Transactions on Automatic Control, 57, 9, 2348-2354, (2012) · Zbl 1369.90122
[19] Lu, J.; Tang, C. Y.; Regier, P. R.; Bow, T. D., Gossip algorithms for convex consensus optimization over networks, IEEE Transactions on Automatic Control, 56, 12, 2917-2923, (2011) · Zbl 1368.90023
[20] Meng, W.; Xiao, W.; Xie, L., A projection based fully distributed approach for source localization in wireless sensor networks, Adhoc & Sensor Wireless Networks, 18, 1-2, 131-158, (2013)
[21] Nedić, A.; Ozdaglar, A., Approximate primal solutions and rate analysis for dual subgradient methods, SIAM Journal on Optimization, 19, 4, 1757-1780, (2008) · Zbl 1191.90037
[22] Nedić, A.; Ozdaglar, A., Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 54, 1, 48-61, (2009) · Zbl 1367.90086
[23] Nedić, A.; Ozdaglar, A.; Parrilo, P. A., Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 55, 4, 922-938, (2010) · Zbl 1368.90143
[24] Pardalos, P. M.; Romeijn, H. E., Handbook of global optimization. vol. 2, (2002), Kluwer Academic Publishers London · Zbl 0991.00017
[25] Rockafellar, R. T., Convex analysis, (1972), Princeton University Press New Jersey · Zbl 0224.49003
[26] Shi, G.; Johansson, K. H., Randomized optimal consensus of multi-agent systems, Automatica, 48, 12, 3018-3030, (2012) · Zbl 1256.93012
[27] Shi, G.; Johansson, K. H., Multi-agent robust consensus: convergence analysis and application, SIAM Journal on Control and Optimization, 51, 5, 3673-3691, (2013) · Zbl 1279.93013
[28] Shi, G.; Johansson, K. H.; Hong, Y., Reaching an optimal consensus: dynamical systems that compute intersections of convex sets, IEEE Transactions on Automatic Control, 58, 3, 610-622, (2013) · Zbl 1369.93049
[29] Wang, J., & Elia, N. (2010). Control approach to distributed optimization. In Forty-Eighth annual allerton conference (pp. 557-561).
[30] Wang, J., & Elia, N. (2011). A control perspective for centralized and distributed convex optimization. In 50th IEEE conference on decision and control and European control conference (pp. 3800-3805).
[31] Zhang, Y.; Lou, Y.; Hong, Y.; Xie, L., Distributed projection-based algorithms for source localization in wireless sensor networks, IEEE Transactions on Wireless Communications, 14, 6, 3131-3142, (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.