分布式一致性最優化的梯度算法與收斂分析

梁舒; 彭開香

doi:10.13374/j.issn2095-9389.2019.09.05.005

分布式一致性最優化的梯度算法與收斂分析

doi: 10.13374/j.issn2095-9389.2019.09.05.005

梁舒^,,
彭開香

北京科技大學自動化學院工業過程知識自動化教育部重點實驗室，北京 100083

基金項目: 國家自然科學基金資助項目（61903027，61873024）

詳細信息

通訊作者:
E-mail：sliang@ustb.edu.cn

中圖分類號: TP27
計量
- 文章訪問數: 2978
- HTML全文瀏覽量: 2052
- PDF下載量: 130
- 被引次數: 0
出版歷程
- 收稿日期: 2019-09-05
- 刊出日期: 2020-04-01

Distributed gradient-based consensus optimization algorithm and convergence analysis

LIANG Shu^,,
PENG Kaixiang

Key Laboratory of Knowledge Automation for Industrial Processes of Ministry of Education, School of Automation, University of Science and Technology Beijing, Beijing 100083, China

More Information

Corresponding author: E-mail: sliang@ustb.edu.cn

摘要

摘要: 研究了多智能體網絡中受集合約束的一致性最優化問題，提出了基于原始–對偶梯度的定步長分布式算法。算法中包括步長在內的參數會影響收斂性，需要先進行收斂分析，再根據收斂條件設置合適的參數。本文首先針對一般的定步長迭代格式，提出一種基于李雅普諾夫函數的收斂分析范式，它類似于一般微分方程關于李雅普諾夫穩定的分析方法。然后，針對所考慮的分布式梯度算法，構造了合適的李雅普諾夫函數，并根據收斂條件得到了算法參數設定范圍，避免了繁冗復雜的分析論證。本文提出的理論與方法也為其他類型的分布式算法提供了一個框架性、系統性的論證方法。
- 分布式優化 /
- 原始–對偶 /
- 收斂分析 /
- 李雅普諾夫函數 /
- 一致性
Abstract: A distributed optimization problem is cooperatively solved by a network of agents, which have significant applications in many science and engineering fields, such as metallurgical engineering. For complex industrial processes with multiple-level characteristics, varying working conditions, and long processes, numerous optimization decision-making micro and macro control problems, such as product quality control, production planning, scheduling, and energy comprehensive deployment, are encountered. The theory and method of distributed optimization are keys to promoting the strategic decision-making of the integration of industrialization and new-generation industrial revolution. Their development enhances the ability to deal with large-scale and complex problems of big data, which have important practical value and economic benefits. In this study, consensus optimization with set constraints in multi-agent networks was explored. A distributed algorithm with a fixed step size was proposed on the basis of a primal-dual gradient scheme. Parameters such as step size affect the convergence of the algorithm. As such, convergence should be analyzed first, and appropriate parameters should be subsequently set in accordance with convergence conditions. Existing works have constructed different Lyapunov functions by exploiting the specific iteration scheme of this algorithm and analyzing convergence. Conversely, a convergence analysis paradigm based on a Lyapunov function was proposed in this study for general fixed step size iteration schemes, which were similar to the analysis method of Lyapunov convergence for general differential equations. A suitable Lyapunov function was constructed for the distributed gradient algorithm, and a parameter setting range was obtained in accordance with the convergence conditions. The proposed method avoids the tedious and complicated analysis of algorithm convergence and parameter assignment. The theory and method presented in this study also provide a framework and systematic demonstration method for other types of distributed algorithms and may be regarded as future directions of distributed optimization.
- distributed optimization /
- primal-dual /
- convergence analysis /
- Lyapunov function /
- consensus

HTML全文

圖 1 信息分享關系圖

Figure 1. Information sharing graph

下載: 全尺寸圖片幻燈片

圖 2 決策變量的更新軌跡

Figure 2. Trajectories of decision variables

下載: 全尺寸圖片幻燈片

圖 3 對偶變量的更新軌跡

Figure 3. Trajectories of dual variables

下載: 全尺寸圖片幻燈片

圖 4 李雅普諾夫函數的更新軌跡

Figure 4. Trajectory of the Lyapunov function

下載: 全尺寸圖片幻燈片

259luxu-164

參考文獻(19)

[1]	Yang T, Yi X L, Wu J F, et al. A survey of distributed optimization. Ann Rev Control, 2019, 47: 278 doi: 10.1016/j.arcontrol.2019.05.006
[2]	Yi P, Hong Y G. Distributed cooperative optimization and its applications. Sci Sin Math, 2016, 46(10): 1547 衣鵬, 洪奕光. 分布式合作優化及其應用. 中國科學: 數學, 2016, 46(10):1547
[3]	Peng K X, Zhang C F, Ma L, et al. System-levels-based holographic fault diagnosis for complex industrial processes. CIESC J, 2019, 70(2): 590 彭開香, 張傳放, 馬亮, 等. 面向系統層級的復雜工業過程全息故障診斷. 化工學報, 2019, 70(2):590
[4]	Nedic A, Ozdaglar A, Parrilo P A. Constrained consensus and optimization in multi-agent networks. IEEE Trans Autom Control, 2010, 55(4): 922 doi: 10.1109/TAC.2010.2041686
[5]	Nedic A, Olshevsky A. Distributed optimization over time-varying directed graphs. IEEE Trans Autom Control, 2015, 60(3): 601 doi: 10.1109/TAC.2014.2364096
[6]	Nedic A, Olshevsky A. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans Autom Control, 2016, 61(12): 3936 doi: 10.1109/TAC.2016.2529285
[7]	Shi W, Ling Q, Wu G, et al. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM J Optim, 2015, 25(2): 944 doi: 10.1137/14096668X
[8]	Nedic A, Olshevsky A, Shi W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J Optim, 2017, 27(4): 2597 doi: 10.1137/16M1084316
[9]	Liu Q S, Yang S F, Hong Y G. Constrained consensus algorithms with fixed step size for distributed convex optimization over multi-agent networks. IEEE Trans Autom Control, 2017, 62(8): 4259 doi: 10.1109/TAC.2017.2681200
[10]	Lei J L, Chen H F, Fang H T. Primal-dual algorithm for distributed constrained optimization. Syst Control Lett, 2016, 96: 110 doi: 10.1016/j.sysconle.2016.07.009
[11]	Liang S, Wang L Y, Yin G. Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity. Automatica, 2019, 105: 298 doi: 10.1016/j.automatica.2019.04.004
[12]	Gharesifard B, Cortes J. Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans Autom Control, 2014, 59(3): 781 doi: 10.1109/TAC.2013.2278132
[13]	Zeng X L, Yi P, Hong Y G. Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans Autom Control, 2017, 62(10): 5227 doi: 10.1109/TAC.2016.2628807
[14]	Yang S F, Liu Q S, Wang J. A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Trans Autom Control, 2017, 62(7): 3461 doi: 10.1109/TAC.2016.2610945
[15]	Deng Z H, Liang S, Hong Y G. Distributed continuous-time algorithms for resource allocation problems over weight-balanced digraphs. IEEE Trans Cybern, 2018, 48(11): 3116 doi: 10.1109/TCYB.2017.2759141
[16]	Liang S, Zeng X L, Hong Y G. Distributed nonsmooth optimization with coupled inequality constraints via modified Lagrangian function. IEEE Trans Autom Control, 2018, 63(6): 1753 doi: 10.1109/TAC.2017.2752001
[17]	Hiriart-Urruty J B, Lemaréchal C. Convex Analysis and Minimization Algorithms I: Fundamentals. Springer Science & Business Media, 2013
[18]	Nesterov Y. Lectures on Convex Optimization. Springer, 2018
[19]	Godsil C, Royle G F. Algebraic Graph Theory. Springer Science & Business Media, 2013