Averaging approach to distributed convex optimization for continuous-time multi-agent systems

Ni, Wei   ; Wang, Xiaoli

Kybernetika, Tome 52 (2016) no. 6, pp. 898-913

Abstract (VO)

Recently, distributed convex optimization has received much attention by many researchers. Current research on this problem mainly focuses on fixed network topologies, without enough attention to switching ones. This paper specially establishes a new technique called averaging-base approach to design a continuous-time distributed algorithm for convex optimization problem under switching topology. This idea of using averaging was proposed in our earlier works for the consensus problem of multi-agent systems under switching topology, and it is further developed in this paper to gain further insight into the distributed optimization algorithm. Key techniques are used, such as two-time-scale analysis and asymptotic expansions for the solutions of the backward equation or Liouvill equation. Important results are obtained, including weak convergence of our algorithm to the optimal solution.

Détail

DOI : 10.14736/kyb-2016-6-0898

Classification : 93C15, 93C35
Keywords: distributed convex optimization; averaging approach; two-time-scale; Markovian switching; invariant measure

Bibliographie

[1] Bertsekas, D. P., Tsitsiklis, J. N.: Neuro-Dynamic Programming. Athena Scientific, Belmont 1996. | Zbl

[2] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004. | DOI | MR | Zbl

[3] Evans, L. C.: Partial Differential Equations. Second edition. American Math Society, 2010. | MR

[4] Feijer, D., Paganini, F.: Stability of primal-dual gradient dynamics and applications to network optimization. Automatica 46 (2010), 1974-1981. | DOI | MR | Zbl

[5] Freedman, D.: Markov Chains. Springer-Verlag, New York 1983. | DOI | MR | Zbl

[6] Gharesifard, B., Cortes, J.: Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans. Automat. Control 59 (2014), 781-786. | DOI | MR

[7] Golshtein, F. G., Yakov, N. V.: Modified Lagrangians and Moonotone Maps in Optimization. Wiley, New York 1996. | MR

[8] Kushner, K. J.: Approximation and Weak Convergence Methods for Random Processes with Applications to Stochastic Systems Theory. The MIT Press, London 1984. | MR | Zbl

[9] Liu, S., Qiu, Z., Xie, L.: Continuous-time distributed convex optimization with set constraints. In: Proc. 19th IFAC World Congress, Cape Town 2014, pp. 9762-9767. | DOI

[10] Liu, Q., Wang, J.: A second-order multi-agent network for bounded-constrained distributed optimization. IEEE Trans. Automat. Control 60 (2015), 3310-3315. | DOI | MR

[11] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. | DOI | MR | Zbl

[12] Lu, J., Tang, C. Y.: Zero-gradient-sum algorithms for distributed convex: the continuous-time case. IEEE Trans. Automat. Control 57 (2012), 2348-2354. | DOI | MR

[13] Mateos-Nunez, D., Cortes, J.: Noise-to-state exponential stable distributed convex optimization on weight-balanced digraphs. SIAM J.n Control Optim. 54 (2016), 266-290. | DOI | MR

[14] Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54 (2009), 48-61. | DOI | MR

[15] Nedic, A., Ozdaglar, A., Parrilo, P. A.: Constained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938. | DOI | MR

[16] Pavliotis, G. V., Stuart, A. M.: Multiscale methods: averaging and homogenization. Springer-Verlag, New York 2008. | MR | Zbl

[17] Ni, W., Wang, Xiaoli, Xiong, Chun: Leader-following consensus of multiple linear systems under switching topologies: an averaging method. Kybernetika 48 (2012), 1194-1210. | MR | Zbl

[18] Ni, W., Wang, X., Xiong, C.: Consensus controllability, observability and robust design for leader-following linear multi-agent systems. Automatica 49 (2013), 2199-2205. | DOI | MR

[19] Ni, W., Zhao, D., Ni, Y., Wang, X.: Stochastic averaging approach to leader-following consensus of linear multi-agent systems. J. Franklin Inst. 353 (2016), 2650-2669. | DOI | MR | Zbl

[20] Nowak, R. D.: Distributed EM algorithms for density estimation and clustering in sensor networks. IEEE Trans. Signal Process. 51 (2003), 2245-2253. | DOI

[21] Tanabe, K.: A geometric method in nonlinear programming. J. Optim. Theory Appll. 30 (1980), 181-210. | DOI | MR | Zbl

[22] Touri, B., Gharesifard, B.: Continuous-time distributed convex optimization on time-varying directed networks. In: 54th IEEE Conference on Decision and Control, Osaka 2015, pp. 724-729. | DOI

[23] Wang, J., Elia, N.: Control approach to distributed optimization. In: 48th Annual Allerton Conference on Communication, Control, and Computing 2010, pp. 557-561. | DOI

[24] Wang, J., Elia, N.: A control perspective for centralized and distributed convex optimization. In: 50th IEEE Conference on Decision and Control and European Control Conference, Orlando 2011, pp. 3800-3805.

[25] Wang, X., Yi, P., Hong, Y.: Dynamic optimization for multi-agent systems with external disturbances. Control Theory Technol. 12 (2014), 132-138. | DOI | MR

[26] Yi, P., Zhang, Y., Hong, Y.: Potential game design for a class of distributed optimisation problems. J. Control Decision 1 (2014), 166-179. | DOI

[27] Yi, P., Hong, Y., Liu, F.: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. | DOI | MR | Zbl

[28] Yi, P., Hong, Y., Liu, F.: Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and its application to economic dispatch of power systems. Automatica 74 (2016), 259-269. | DOI | MR

[29] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. arXiv:1510.07386v2, 2016.