基于事件触发的分布式优化算法

杨涛; 徐磊; 易新蕾; 张圣军; 陈蕊娟; 李渝哲

doi:10.16383/j.aas.c200838

基于事件触发的分布式优化算法

doi: 10.16383/j.aas.c200838 cstr: 32138.14.j.aas.c200838

杨涛^1,,
徐磊^1,,
易新蕾^2,,
张圣军^3,,
陈蕊娟^4,,
李渝哲^1,

1.
东北大学流程工业综合自动化国家重点实验室中国沈阳 110819
2.
瑞典皇家理工学院电气工程与计算机科学学院决策与控制系统系瑞典斯德哥尔摩 10044
3.
北德克萨斯大学电气工程系美国德克萨斯州丹顿 76203
4.
华中科技大学人工智能与自动化学院中国武汉 430074

基金项目: 国家自然科学基金委重大项目(61991400, 61991403, 61991404, 61890924)资助

详细信息

作者简介:
杨涛：东北大学流程工业综合自动化国家重点实验室教授. 主要研究方向为工业人工智能, 信息物理系统, 分布式协同控制和优化. E-mail: yangtao@mail.neu.edu.cn

徐磊：东北大学流程工业综合自动化国家重点实验室博士研究生. 主要研究方向为分布式控制及优化, 网络化系统, 马尔科夫跳变系统. E-mail: 2010345@stu.neu.edu.cn

易新蕾：瑞典皇家理工学院电气工程与计算机科学学院博士后. 主要研究方向为在线优化, 分布式优化, 事件驱动控制. E-mail: xinleiy@kth.se

张圣军：北德州大学电气工程专业博士研究生. 主要研究方向为分布式优化, 统计学习, 稀疏主成分分析. E-mail: ShengjunZhang@my.unt.edu

陈蕊娟：华中科技大学人工智能与自动化学院博士研究生. 主要研究方向为基于动力系统的优化算法的设计和理论分析. E-mail: ruijuancheni@hust.edu.cn

李渝哲：东北大学流程工业综合自动化国家重点实验室教授. 主要研究方向为网络化系统, 信息物理系统, 人工智能与信息安全. 本文通信作者. E-mail: yuzheli@mail.neu.edu.cn

计量
- 文章访问数: 2785
- HTML全文浏览量: 1720
- PDF下载量: 867
- 被引次数: 0
出版历程
- 收稿日期: 2020-10-10
- 录用日期: 2021-01-26
- 网络出版日期: 2021-03-02
- 刊出日期: 2022-01-25

Event-triggered Distributed Optimization Algorithms

1.
State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China
2.
The Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm, 10044, Sweden
3.
The Department of Electrical Engineering, University of North Texas, Denton, TX 76203, USA
4.
School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: Supported by Major Program of National Natural Science Foundation of China (61991400, 61991403, 61991404, 61890924)

More Information

Author Bio:
YANG Tao　Professor at the State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, China. His research interest covers industrial artificial intelligence, cyber physical system, distributed collaborative control and optimization

XU Lei　Ph. D. candidate at the State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, China. His research interest covers distributed control and optimization, network system, and Markovian jump systems

YI Xin-Lei　Postdoctor at the School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Sweden. His research interest covers online optimization, distributed optimization, and event-triggered control

ZHANG Sheng-Jun　Ph. D. candidate in the Department of Electrical Engineering, University of North Texas, USA. His research interest covers distributed optimization, statistical learning, and Sparse PCA

CHEN Rui-Juan　Ph. D. candidate at the School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, China. Her research interest covers the design and theoretical analysis of optimization algorithm based on dynamic system

LI Yu-Zhe　Professor at the State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, China. His research interest covers network system, cyber physical system, artificial intelligence, and information security. Corresponding author of this paper

摘要

摘要: 本文研究了一类分布式优化问题, 其目标是通过局部信息交换使由局部成本函数之和构成的全局成本函数最小. 针对无向连通图, 我们提出了两种基于比例积分策略的分布式优化算法. 在局部成本函数可微且凸的条件下, 证明了所提算法渐近收敛到全局最小值点. 更进一步, 在局部成本函数具有局部Lipschitz梯度和全局成本函数关于全局最小值点是有限强凸的条件下, 证明了所提算法的指数收敛性. 此外, 为了避免智能体之间的连续通信和减少通信负担, 将所提的两种分布式优化算法与事件触发通信相结合, 提出了两种基于事件触发的分布式优化算法. 证明了提出的事件触发优化算法不存在Zeno行为, 并且在相应条件下保持了与连续通信下分布式优化算法一样的收敛性. 最后, 通过数值仿真验证了上述理论结果.
- 分布式优化 /
- 事件触发通信 /
- Zeno行为 /
- 比例积分算法
Abstract: This paper studies a class of distributed optimization problems, whose objective is to minimize the global cost function formed by a sum of local cost functions through local information exchanges. For undirected connected graphs, we propose two distributed optimization algorithms based on the proportional-integral feedback mechanism. Under the condition that the local cost functions are differentiable and convex, it is proved that the proposed algorithms asymptotically converge to a global minimum. For the case that the local cost functions have local Lipschitz gradient and the global cost function is strongly convex with respect to the global minimum, the exponential convergences of the two distributed optimization algorithms are established. In addition, in order to avoid continuous communication between agents and reduce communication burden, by integrating the two proposed distributed optimization algorithms with event-triggered communications, two event-triggered based distributed optimization algorithms are developed. It is shown that the two proposed event-triggered optimization algorithms are free of Zeno behavior. Moreover, the two proposed event-triggered based distributed optimization algorithms maintain the same convergence properties as the distributed optimization algorithms with continuous communications under the corresponding conditions. Finally, the above theoretical results are verified by numerical simulations.
- Distributed optimization /
- event-triggered communications /
- Zeno behavior /
- proportional-integral algorithm
注释:

1) 收稿日期 2020-10-10 录用日期 2021-01-26 Manuscript received October 10, 2020; accepted January 26,2021 国家自然科学基金委重大项目 (61991400, 61991403, 61991404, 61890924)资助 Supported by Major Program of National Natural Science Foundation of China (61991400, 61991403, 61991404, 61890924) 本文责任编委贺威 Recommended by Associate Editor HE Wei 1. 东北大学流程工业综合自动化国家重点实验室沈阳 110819 中国 2. 瑞典皇家理工学院电气工程与计算机科学学院决策与控制系统系斯德哥尔摩 10044 瑞典 3. 北德克萨斯大学电气工程系德克萨斯州丹顿 76203 美国 4. 华中科技大学人工智能与自动化学院武汉 430074 中国 1. State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China 2. The Division of Decision and Control Systems, School ofElectrical Engineering and Computer Science, KTH Royal Institute

2) of Technology, Stockholm 10044, Sweden 3. The Department of Electrical Engineering, University of North Texas, Denton, TX 76203, USA 4. School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

HTML全文

图 1 不同算法中$\sum\nolimits_{i = 1}^{50}\|x_{i}(t)-x^{*}\|^{2}$的演化

Fig. 1 The state evolution of $\sum\nolimits_{i = 1}^{50}\|x_{i}(t)-x^{*}\|^{2}$ in various algorithms

下载: 全尺寸图片幻灯片

图 2 算法(4)中智能体6, 16, 26, 36, 46的状态演化

Fig. 2 State evolutions of agents 6, 16, 26, 36, 46 of Algorithm (4)

下载: 全尺寸图片幻灯片

图 3 算法(6)中智能体6, 16, 26, 36, 46的状态演化

Fig. 3 State evolutions of agents 6, 16, 26, 36, 46 of Algorithm (6)

下载: 全尺寸图片幻灯片

参考文献(53)

[1]	Tsitsiklis J N. Problems in decentralized decision making and computation [Ph. D. dissertation], MIT, Cambridge, MA, 1984
[2]	Tsitsiklis J N, Bertsekas D P, Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 1986, 31(9): 803--812 doi: 10.1109/TAC.1986.1104412
[3]	洪奕光, 张艳琼. 分布式优化: 算法设计和收敛性分析. 控制理论与应用, 2014, 31: 850--857 doi: 10.7641/CTA.2014.40012 Hong Yi-Guang, Zhang Yan-Qiong. Distributed optimization: algorithm design and convergence analysis. Control Theory & Applications, 2014, 31: 850--857(in Chinese) doi: 10.7641/CTA.2014.40012
[4]	衣鹏, 洪奕光. 分布式合作优化及其应用. 中国科学: 数学, 2016, 46(10): 1547--1564 Yi Peng, and Hong Yi-Guang. Distributed cooperative optimization and its applications. SCIENTIA SINICA Mathematica, 2016, 46(10): 1547--1564(in Chinese)
[5]	谢佩, 游科友, 洪奕光, 谢立华. 网络化分布式凸优化算法研究进展. 控制理论与应用, 2018, 35(7): 918--927 doi: 10.7641/CTA.2018.80205 Xie Pei, You Ke-You, Hong Yi-Guang, Xie Li-Hua. A survey of distributed convex optimization algorithms over networks. Control Theory & Application, 2018, 35(7): 918--927(in Chinese) doi: 10.7641/CTA.2018.80205
[6]	Nedić A, Olshevsky A, Rabbat M G. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 2018, 106(5): 953--976 doi: 10.1109/JPROC.2018.2817461
[7]	王龙, 卢开红, 关永强. 分布式优化的多智能体方法. 控制理论与应用, 2019, 36(11): 1820--1883 doi: 10.7641/CTA.2019.90502 Wang Long, Lu Kai-Hong, and Guan Yong-Qiang. Distributed optimization via multi-agent systems. Control Theory & Applications, 2019, 36(11): 1820--1883(in Chinese) doi: 10.7641/CTA.2019.90502
[8]	Yang T, Yi X L, Wu J F, Yuan Y, Wu D, Meng Z Y, et al A survey of distributed optimization. Annual Reviews in Control, 2019, 47: 278--305 doi: 10.1016/j.arcontrol.2019.05.006
[9]	Khan U A, Bajwa W U, Nedić A, Rabbat M G, Sayed A H. Optimization for Data-Driven Learning and Control. Proceedings of the IEEE, 2020, 108(11): 1863--1868 doi: 10.1109/JPROC.2020.3031225
[10]	杨涛, 柴天佑. 分布式协同优化的研究现状与展望. 中国科学: 技术科学, 2020, 50(11): 1414--1425 doi: 10.1360/SST-2020-0040 Yang Tao, Chai Tian-You. Research status and prospects of distributed collaborative optimization. SCIENTIA SINICA Technologica, 2020, 50(11): 1414--1425(in Chinese) doi: 10.1360/SST-2020-0040
[11]	Johansson B, Keviczky T, Johansson M, Johansson K H. Subgradient methods and consensus algorithms for solving convex optimization problems. In: Proceedings of the IEEE Conference on Decision and Control, Cancun, Mexico: IEEE, 2008. 4185−4190
[12]	Nedić A, Ozdaglar A. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 2009, 54(1): 48--61 doi: 10.1109/TAC.2008.2009515
[13]	Zhu M, Martínez S. On distributed convex optimization under inequality and equality constraints. IEEE Transactions on Automatic Control, 2012, 57(1): 151--164 doi: 10.1109/TAC.2011.2167817
[14]	Nedić A, Olshevsky A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 2015, 60(3): 601--615 doi: 10.1109/TAC.2014.2364096
[15]	Yang T, Lu J, Wu D, Wu J, Shi G, Meng Z, Johansson K H. A distributed algorithm for economic dispatch over time-varying directed networks with delays. IEEE Transactions on Industrial Electronics, 2017, 64(6): 5095--5106 doi: 10.1109/TIE.2016.2617832
[16]	Matei I, Baras J S. Performance evaluation of the consensus-based distributed subgradient method under random communication topologies. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(4): 754--771 doi: 10.1109/JSTSP.2011.2120593
[17]	Yuan K, Ling Q, Yin W. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 2015, 26(3): 1835--1854
[18]	Shi W, Ling Q, Wu G, Yin W. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 2015, 25(2): 944--966 doi: 10.1137/14096668X
[19]	Yao L, Yuan Y, Sundaram S, Yang T. Distributed finite-time optimization. In: Proceedings of the 14th International Conference on Control and Automation. Anchorage, AK, USA: IEEE, 2018. 147−154
[20]	Qu G, Li N. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 2018, 5(3): 1245--1260 doi: 10.1109/TCNS.2017.2698261
[21]	Xu J, Zhu S, Soh Y C, Xie L. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In: Proceedings of the 54th IEEE Conference on Decision and Control. Osaka, Japan: IEEE, 2015. 2055−2060
[22]	Yang S, Tan S, Xu J X. Consensus based approach for economic dispatch problem in a smart grid. IEEE Transactions on Power Systems, 2013, 28(4): 4416--4426 doi: 10.1109/TPWRS.2013.2271640
[23]	Du W, Yao L, Wu D, Li X, Liu G, Yang T. Accelerated distributed energy management for microgrids. In: Proceedings of the 2018 IEEE Power & Energy Society General Meeting. Portland, OR, USA: IEEE, 2018. 1−5
[24]	Pu S, Shi W, Xu J, Nedić A. A push-pull gradient method for distributed optimization in networks. In: Proceedings of the 57th IEEE Conference on Decision and Control. Miami, FL, USA: IEEE, 2018. 3385−3390
[25]	Xin R, Khan U A. A linear algorithm for optimization over directed graphs with geometric convergence. IEEE Control Systems Letters, 2018, 2(3): 325--330
[26]	Zhu M, Martínez S. Discrete-time dynamic average consensus. Automatica, 2010, 46(2): 322--329 doi: 10.1016/j.automatica.2009.10.021
[27]	Wang J, Elia N. Control approach to distributed optimization. In: Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. Allerton, Illinois, USA: IEEE, 2010. 557−561
[28]	Gharesifard B, Cortés J. Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Transactions on Automatic Control, 2014, 59(3): 781--786 doi: 10.1109/TAC.2013.2278132
[29]	Kia S S, Cortés J, Martínez S. Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica, 2015, 55: 254--264 doi: 10.1016/j.automatica.2015.03.001
[30]	Lu J, Tang C Y. Zero-gradient-sum algorithms for distributed convex optimization: The continuous-time case. IEEE Transactions on Automatic Control, 2012, 57(9): 2348--2354 doi: 10.1109/TAC.2012.2184199
[31]	Varagnolo D, Zanella F, Cenedese A, Pillonetto G, Schenato L. Newton-Raphson consensus for distributed convex optimization. IEEE Transactions on Automatic Control, 2016, 61(4): 994--1009 doi: 10.1109/TAC.2015.2449811
[32]	Wei E, Ozdaglar A, Jadbabaie A. A distributed Newton method for network utility maximization-I: Algorithm. IEEE Transactions on Automatic Control, 2013, 58(9): 2162--2175 doi: 10.1109/TAC.2013.2253218
[33]	Aström K J, Bernhardsson B M. Comparison of Riemann and Lebesgue sampling for first order stochastic systems. In: Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, USA: IEEE, 2002. 2011−2016
[34]	Tabuada P. Event-triggered real-time scheduling of stabilizing control tasks. IEEE Transactions on Automatic Control, 2007, 52(9): 1680--1685 doi: 10.1109/TAC.2007.904277
[35]	Girard A. Dynamic triggering mechanisms for event-triggered control. IEEE Transactions on Automatic Control, 2015, 60(7): 1992--1997 doi: 10.1109/TAC.2014.2366855
[36]	Dimarogonas D V, Frazzoli E, Johansson K H. Distributed event-triggered control for multi-agent systems. IEEE Transactions on Automatic Control, 2012, 57(5): 1291--1297 doi: 10.1109/TAC.2011.2174666
[37]	Seyboth G S, Dimarogonas D V, Johansson K H. Event-based broadcasting for multi-agent average consensus. Automatica, 2013, 49(1): 245--252 doi: 10.1016/j.automatica.2012.08.042
[38]	Meng X, Xie L, Soh Y C, Nowzari C, Pappas G J. Periodic event-triggered average consensus over directed graphs. In: Proceedings of the 54th IEEE Transactions on Decision and Control. Osaka, Japan: IEEE, 2015. 4151−4156
[39]	Meng X, Xie L, Soh Y C. Asynchronous periodic event-triggered consensus for multi-agent systems. Automatica, 2017, 84: 214--220 doi: 10.1016/j.automatica.2017.07.008
[40]	Yi X. Resource-constrained multi-agent control systems: Dynamic event-triggering, input saturation, and connectivity preservation. [Master thesis], Royal Institute of Technology, Sweden, 2017
[41]	Nowzari C, Cortés J, Pappas G. Event-triggered control for multi-agent average consensus. Cooperative Control of Multi-Agent Systems. John Wiley & Sons, Ltd, 2018, 177−208
[42]	Yi X, Yang T, Wu J, Johansson K H. Distributed event-triggered control for global consensus of multi-agent systems with input saturation. Automatica, 2019, 100: 1--9 doi: 10.1016/j.automatica.2018.10.032
[43]	Liu S, Xie L, Quevedo D E. Event-triggered quantized communication-based distributed convex optimization. IEEE Transactions on Control of Network Systems, 2018, 5(1): 167--178 doi: 10.1109/TCNS.2016.2585305
[44]	Chen W, Ren W. Event-triggered zero-gradient-sum distributed consensus optimization over directed networks. Automatica, 2016, 65: 90--97 doi: 10.1016/j.automatica.2015.11.015
[45]	Du W, Yi X, Jemin G, Johansson K H, Yang T. Distributed optimization with dynamic event-triggered mechanisms. In: Proceedings of the 57th IEEE Conference on Decision and Control, Miami, FL, USA: IEEE, 2018. 969−974
[46]	Yi X, Yao L, Yang T, George J, Johansson K H. Distributed optimization for second-order multi-agent systems with dynamic event-triggered communication. In: Proceedings of the 57th IEEE Conference on Decision and Control, Miami, FL, USA: IEEE, 2018. 3397−3402
[47]	Wang D, Gupta V, Wang W. An event-triggered protocol for distributed optimal coordination of double-integrator multi-agent systems. Neurocomputing, 2018, 319(30): 34--41
[48]	Liu C, Li H, Shi Y, Xu D. Event-triggered broadcasting for distributed smooth optimization. In: Proceedings of the 58th IEEE Conference on Decision and Control, Nice, France: IEEE, 2019. 716−721
[49]	Liu C, Li H, Shi Y, Xu D. Distributed event-triggered gradient method for constrained convex minimization. IEEE Transactions on Automatic Control, 2020, 65(2): 778--785 doi: 10.1109/TAC.2019.2916985
[50]	Li M, Su L, Liu T. Distributed optimization with event-triggered communication via input feedforward passivity. IEEE Control Systems Letters, 2020, 5(1): 283--288
[51]	Johansson K H, Egerstedt M, Lygeros J, Sastry S. On the regularization of Zeno hybrid automata. Systems & Control Letters, 1999, 38(3): 141--150
[52]	Godsi C, Royle G F, Algebraic Graph Theory, ser. Graduate Texts in Mathematics. New York: Springer-Verlag, 2001, 207
[53]	Khalil H K, Nonlinear Systems, 3rd ed. Prentice-Hall, New Jersey, 2002