【作者】 许伟；

【导师】 吴刚；

【作者基本信息】 中国科学技术大学 ， 控制科学与工程， 2019， 硕士

【摘要】 在诸如机器学习,资源分配,数据挖掘,自动控制等等很多领域都需要应用优化算法求解优化问题。而随着大数据,云计算,5G通信,物联网等技术的发展,分布式优化算法的研究得到了越来越多的重视。分布式优化即通过多个智能体组成通信网络,协同求解优化问题的最优解。相比于集中式优化,分布式优化具有更好的灵活性,拓展性,更高的计算能力和存储容量。分布式优化分为有中心优化和无中心优化,本文主要研究有中心网络中的带约束分布式优化算法和无中心网络中的鲁棒动态优化算法。在有中心网络中,中心与一组智能体相连,协同求解一个服从全局和本地约束的目标函数的最优解。该目标函数是所有智能体本地目标函数与全局目标函数之和。本文基于分而治之的思想,提出了两种原对偶分布式算法,一种是基于ADMM的原对偶算法,另一种是原对偶一阶算法(PDFO)。这两种算法将全局目标函数、约束和本地目标函数、约束分别分配到中心层和节点层,这两层在每一时刻交换各自的迭代值,交替求解整个网络目标函数的最优解。相比于现有算法,本文的算法充分利用了中心和节点的计算能力,同时也避免了额外的通信代价。本文证明了PDFO算法的收敛性,并且通过数值仿真验证了这两种算法的收敛性能。在无中心网络中,一组节点相互通信连接成一个网络。每个节点在每一个时刻得到各自的本地目标函数,即该本地目标函数是随时刻变化的。这些节点相互通信,在每一个时刻协同求解所有本地目标函数之和的最优解。本文考虑网络中存在故障节点,这些故障节点向邻居节点发送错误值,从而影响邻居节点对于最优解的估计。为了减轻故障节点的影响,本文在原问题中加入了TV范数正则项,从而得到新的数学模型。该模型使得正常节点的估计值相互靠近,同时允许它们与故障节点发送的错误值不同。本文证明了在一个充分条件满足的情况下,新模型的最优解一致且与原问题的最优解相同。本文提出了分布式次梯度算法来求解每一个时刻TV范数正则问题的最优解。在每一个时刻,正常节点只需求解本地目标函数梯度,并且结合从邻居节点收集来的最优解估计值。在原问题最优解变化有界的情况下,本文证明了跟踪误差有界,即跟踪误差不随着故障节点发送的错误值的增大而增大。通过数值实验,本文验证了所提算法在存在故障节点情况下的鲁棒跟踪表现。更多还原

【Abstract】 There are many fileds that need to apply optimization algorithms to solve optimiza-tion problems,such as machine learning,source allocation,data mining,auto-control,atc.With the development of technology of big data,cloud computing,5G commu-nication and IoT,the research of distributed optimization algorithm is paid more and more attention.Distributed optimization is that multi-agent cooperatively solve the op-timization problem over a network.Compared to centralized optimization,distributed optimization is more flexible and more extensible,has higher computing power and big-ger storage space.Distributed optimization can divided into centralized distributed opti-mization and decentralized distributed optimization,this thesis focus on distributed con-strained optimization over centralized network and robust dynamic optimization over decentralized network.In a centralized network,we consider a distributed constrained optimisation prob-lem where a group of distributed agents are interconnected via a cloud center,and col-laboratively minimise a network-wide objective function subject to local and global constraints.This thesis devotes to developing efficient distributed algorithms that fully utilise the computation abilities of the cloud center and the agents,as well as avoid ex-tensive communications between the cloud center and the agents.We address these is-sues by introducing two divide-and-conquer techniques,the alternating direction method of multipliers(ADMM)and a primal-dual first-order(PDFO)method,which assign the local objective functions and constraints to the agents while the global ones to the cloud center.Both algorithms are proved to be convergent to the primal-dual optimal solu-tion.Numerical experiments demonstrate the effectiveness of the proposed distributed constrained optimisation algorithms.In a decentralized network,we consider the problem of tracking a network-wide solution that dynamically minimizes the summation of time-varying local cost functions of network agents,when some of the agents are malfunctioning.The malfunctioning agents broadcast faulty values to their neighbors,and lead the optimization process to a wrong direction.To mitigate the influence of the malfunctioning agents,we propose a total variation(TV)norm regularized formulation that drives the local variables of the regular agents to be close,while allows them to be different with the faulty values broadcast by the malfunctioning agents.We give a sufficient condition under which consensus of the regular agents is guaranteed,and bound the gap between the consen-sual solution and the optimal solution we pursue as if the malfunctioning agents do not exist A fully decentralized subgradient algorithm is proposed to solve the TV norm reg-ularized problem in a dynamic manner.At every time,every regular agent only needs one subgradient evaluation of its current local cost function,in addition to combining messages received from neighboring regular and malfunctioning agents.The tracking error is proved to be bounded,given that variation of the optimal solution is bounded.Numerical experiments demonstrate the robust tracking performance of the proposed algorithm at presence of the malfunctioning agents.更多还原