×

Necessary and sufficient conditions for distributed constrained optimal consensus under bounded input. (English) Zbl 1390.93074

Summary: In this paper, we study a distributed constrained optimal consensus problem for discrete-time first-order integrator systems under bounded input. Each agent is assigned with a local convex cost function, and all agents are required to achieve consensus at the minimum of the aggregate cost over a common convex constraint set, which is only accessible by part of the agents. A 2-step control protocol is designed to solve the problem under bounded input. Firstly, at each time step, each agent moves a bounded step of the subgradient descent from an individual cost and another one along the projection direction if it can access the constraint. The second movement is then given by a bounded average of the relative positions to neighbors. Specifically, to coordinate the subgradient step within the network without using global information, we introduce an estimate of the upper bound of all agents’ subgradients, which is updated by a unilateral consensus mechanism. Under the given control protocol, we obtain the necessary and sufficient conditions to achieve the constrained optimal consensus for a fixed topology. Under similar conditions, we also solve the problem for switching topologies and conduct a convergence rate analysis for strongly convex costs.

MSC:

93A14 Decentralized systems
93C55 Discrete-time control/observation systems
68T42 Agent technology and artificial intelligence
93E03 Stochastic systems in control theory (general)
Full Text: DOI

References:

[1] CevherV, BeckerS, SchmidtM. Convex optimization for big data: scalable, randomized, and parallel algorithms for big data analytics. IEEE Signal Process Mag. 2014;31(5):32‐43.
[2] SayedAH. Adaptation, learning, and optimization over networks. Mach Learn. 2014;7(4‐5):311‐801. · Zbl 1315.68212
[3] NedićA, OzdaglarA. Distributed subgradient methods for multi‐agent optimization. IEEE Trans Autom Control. 2009;54(1):48‐61. · Zbl 1367.90086
[4] NedićA, OzdaglarA, ParriloP. Constrained consensus and optimization in multi‐agent networks. IEEE Trans Autom Control. 2010;55(4):922‐938. · Zbl 1368.90143
[5] ChenAI, OzdaglarA. A fast distributed proximal‐gradient method. Paper presented at: 2012 50th Annual Allerton Conference, on Communication, Control, and Computing; 2012; Monticello, IL.
[6] DuchiJC, AgarwalA, WainwrightMJ. Dual averaging for distributed optimization: convergence analysis and network scaling. IEEE Trans Autom Control. 2012;57(3):592‐606. · Zbl 1369.90156
[7] VaragnoloD, ZanellaF, CenedeseA, PillonettoG, SchenatoL. Newton‐Raphson consensus for distributed convex optimization. IEEE Trans Autom Control. 2016;61(4):994‐1009. · Zbl 1359.90099
[8] ZhuM, MartinezS. On distributed convex optimization under inequality and equality constraints. IEEE Trans Autom Control. 2012;57(1):151‐164. · Zbl 1369.90129
[9] IutzelerF, BianchiP, CiblatP, HachemW. Explicit convergence rate of a distributed alternating direction method of multipliers. IEEE Trans Autom Control. 2016;61(4):892‐904. · Zbl 1359.90103
[10] LinP, RenW, SongY. Distributed multi‐agent optimization subject to nonidentical constraints and communication delays. Automatica. 2016;65:120‐131. · Zbl 1328.93024
[11] QiuZ, LiuS, XieL. Distributed constrained optimal consensus of multi‐agent systems. Automatica. 2016;68:209‐215. · Zbl 1334.93019
[12] ZengX, YiP, HongY. Distributed continuous‐time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans Autom Control. 2015.
[13] NedićA, OlshevskyA. Distributed optimization over time‐varying directed graphs. IEEE Trans Autom Control. 2015;60(3):601‐615. · Zbl 1360.90262
[14] XiC, KhanUA. Distributed subgradient projection algorithm over directed graphs. IEEE Trans Autom Control. 2017;62(8):3986‐3992. · Zbl 1373.90110
[15] ShiW, LingQ, WuG, YinW. EXTRA: an exact first‐order algorithm for decentralized consensus optimization. SIAM J Optim. 2015;25(2):944‐966. · Zbl 1328.90107
[16] XuJ, ZhuS, SohYC, XieL. Augmented distributed gradient methods for multi‐agent optimization under uncoordinated constant stepsizes. Paper presented at: 2015 54th IEEE Conference on Decision and Control (CDC),IEEE; 2015;Osaka, Japan.
[17] QuG, LiN. Harnessing smoothness to accelerate distributed optimization. IEEE Trans Control Netw Syst. 2017;PP(99):1‐1.
[18] XiC, KhanUA. DEXTRA: a fast algorithm for optimization over directed graphs. IEEE Trans Autom Control. 2017;PP(99):1‐1.
[19] XiC, KhanUA. ADD‐OPT: accelerated Distributed Directed Optimization. arXiv:1607.04757 [math]. 2016.
[20] NedićA, OlshevskyA, ShiW. Achieving geometric convergence for distributed optimization over time‐varying graphs. SIAM J Optim. 2017;27(4):2597‐2633. · Zbl 1387.90189
[21] NedićA, OlshevskyA, ShiW, UribeCA. Geometrically convergent distributed optimization with uncoordinated step‐sizes. IEEE. 2016.
[22] KiaSS, CortésJ, MartínezS. Distributed convex optimization via continuous‐time coordination algorithms with discrete‐time communication. Automatica. 2015;55:254‐264. · Zbl 1377.93018
[23] ZhangY, LouY, HongY, XieL. Distributed projection‐based algorithms for source localization in wireless sensor networks. IEEE Trans Wirel Commun. 2015;14(6):3131‐3142.
[24] ZhangY, DengZ, HongY. Distributed optimal coordination for multiple heterogeneous Euler-Lagrangian systems. Automatica. 2017;79:207‐213. · Zbl 1371.93025
[25] DengZ, HongY. Multi‐agent optimization design for autonomous Lagrangian systems. Un Sys. 2016;04(01):5‐13.
[26] WangY‐W, BianT, XiaoJW, WenC. Global synchronization of complex dynamical networks through digital communication with limited data rate. IEEE Trans Neural Netw Learn Syst. 2015;26(10):2487‐2499.
[27] JohanssonB, SperanzonA, JohanssonM, JohanssonKH. On decentralized negotiation of optimal consensus. Automatica. 2008;44(4):1175‐1179. · Zbl 1283.93021
[28] WangX, GarciaE, KingstonD, CasbeerD. Consensus‐based simultaneous arrival of multiple UAVs with constrained velocity. Paper presented at: 2015 American Control Conference (ACC); 2015; Chicago, IL.
[29] YangT, MengZ, DimarogonasDV, JohanssonKH. Global consensus for discrete‐time multi‐agent systems with input saturation constraints. Automatica. 2014;50(2):499‐506. · Zbl 1364.93036
[30] SuH, ChenMZQ, LamJ, LinZ. Semi‐global leader‐following consensus of linear multi‐agent systems with input saturation via low gain feedback. IEEE Trans Circuits Syst Regul Pap. 2013;60(7):1881‐1889. · Zbl 1468.93035
[31] ZhaoZ, LinZ. Semi‐global leader‐following consensus of multiple linear systems with position and rate limited actuators. Int J Robust Nonlinear Control. 2015;25(13):2083‐2100. · Zbl 1328.93044
[32] AbdessameudA, TayebiA. On consensus algorithms design for double integrator dynamics. Automatica. 2013;49(1):253‐260. · Zbl 1257.93002
[33] AbdessameudA, TayebiA. Synchronization of networked Lagrangian systems with input constraints. IFAC Proceedings Volumes. 2011;44(1):2382‐2387.
[34] WangQ, GaoH. Global consensus of multiple integrator agents via saturated controls. J Franklin Inst. 2013;350(8):2261‐2276. · Zbl 1293.93064
[35] ZhaoZ, LinZ. Global leader‐following consensus of a group of general linear systems using bounded controls. Automatica. 2016;68:294‐304. · Zbl 1334.93024
[36] QiuZ, HongY, XieL. Optimal consensus of Euler‐Lagrangian systems with kinematic constraints. IFAC‐PapersOnLine. 2016;49(22):327‐332.
[37] XieY, LinZ. Global optimal consensus for multi‐agent systems with bounded controls. Syst Control Lett. 2017;102:104‐111. · Zbl 1377.93022
[38] Hiriart‐UrrutyJ‐B, LemaréchalC. Fundamentals of Convex Analysis. Berlin, Germany: Springer Science & Business Media; 2001. · Zbl 0998.49001
[39] MellingerD, MichaelN, KumarV. Trajectory generation and control for precise aggressive maneuvers with quadrotors. The Int J Robot Res. 2012;31(5):664‐674.
[40] JakoveticD, XavierJ, MouraJMF. Cooperative convex optimization in networked systems: augmented Lagrangian algorithms with directed gossip communication. IEEE Trans Signal Process. 2011;59(8):3889‐3902. · Zbl 1392.94018
[41] JadbabaieD, LinJ, MorseA. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans Autom Control. 2003;48(6):988‐1001. · Zbl 1364.93514
[42] ZhuM, MartínezS. Discrete‐time dynamic average consensus. Automatica. 2010;46(2):322‐329. · Zbl 1205.93014
[43] LiuS, QiuZ, XieL. Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica. 2017;83:162‐169. · Zbl 1373.93023
[44] LiuS, XieL, ZhangH. Distributed consensus for multi‐agent systems with delays and noises in transmission channels. Automatica. 2011;47(5):920‐934. · Zbl 1233.93007
[45] SenetaE. Non‐Negative Matrices and Markov Chains. Berlin, Germany: Springer Science & Business Media; 2006. · Zbl 1099.60004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.