[科普中国]-分布式优化

简介

近年来，随着高科技的蓬勃发展,特别是云计算和大数据等新兴领域的出现。分布式优化理论和应用得到了越来越多的重视，并逐渐渗透到科学研究、工程应用和社会生活的各个方面，分布式优化是通过多智能体之间的合作协调有效地实现优化的任务，可用来解决许多集中式算法难以胜任的大规模复杂的优化问题。如今如何设计出有效的分布式优化算法并对其进行收敛性和复杂性的分析成了优化研究的主要任务之一。与集中式算法的主要区别在于分布式算法还不得不考虑通讯和协调在优化中起到的重要作用。1

发展背景优化与博弈是运筹学和控制论理论研究中的核心问题之一, 同时还在包括系统科学、人工智能、生物生
态、压缩感知、计算机通讯等很多领域有着广泛的应用。 已有成熟的优化与博弈算法大多是集中式的，但是随着现代科学的发展, 在生物、物理、社会和工程等众多学科中出现了许多新问题亟待解决, 包括如何有效处理大数据、进行云计算等。 另外, 通信和微电子技术也在迅猛发展, 为此提供了大量的高效、廉价且性能稳定的传感器、处理器以及各种执行器件, 这极大地支持和拓展了各种分布式算法的应用范围, 促进分布式优化的理论研究不断取得新的成果。
现在随着多智能体(multi-agent)系统理论和协调技术的发展, 许多分布式优化算法可以通过借助多智能体网络的方式来实现。 多智能体系统是由一群具备一定的感知、通信、计算和执行能力的智能个体通过通讯等方式关联成的网络系统。从某种意义上说,分布式技术与多智能体网络是一对孪生兄弟, 或者是一个事物的两个不同的侧面: 分布式强调技术实现的一个事物的两个不同的侧面: 分布式强调技术实现的系统, 分布式方法比传统集中式方法更为灵活且操作更为方便, 这也使得分布式优化与控制的研究得到了迅速发展. 而且已被越来越多的工业和国防应用领域,包括智能电网、传感器网络、社会网络、信息物理系统(cyber-physical system)等所关注。

分布式优化理论和应用已经成为当代系统和控制科学的重要发展方向之一。在优化理论研究过程中,优化算法的设计、收敛性的证明、复杂性(包括分析复杂性和算术复杂性)的分析是其中几个关键性的研究问题. 在分布式优化中, 相应的问题正在吸引着来自诸多领域的科技工作者的巨大研究兴趣. 近年来相关的研究人员在分布式优化上已经取得了一系列重要成果(特别是对一些典型分布式算法收敛性等的分析), 并在不同科研领域中的多种期刊和会议上发表。
现在的分布式优化有两大类研究问题: 一类是对性能指标函数的优化， 另一类是对系统动态过程的优化。 由于分布式优化刚刚兴起，主要的突出理论研究成果还是属于第一类优化中。在一些重要的现实问题中, 比如资源分配, 传感器网络中的定位等问题，每个个体往往有一个代价函数， 且整个网络的代价由这些个体的代价函数和来表示。此网络的目的是通过个体间的局部信息交流而完成整个网络代价函数的优化。其中每个个体只知道自己的代价函数，在给定的分布式优化算法下可以得出保证其收敛的条件。 另一类是对系统动态过程的优化，此类分布式优化问题往往涉及到分布式的(随机)动态规划， 现在虽然已经有些研究， 但大多结果往往是初步的或因所需条件很强难以做深入的理论分析。
在优化理论发展过程中, 凸优化因为其基本且简单一直受到广泛的关注, 很多实际的优化问题都转化或近似成凸优化问题来做。主要有

1）无约束凸优化;

2) 带约束凸优化;

3) 博弈和Nash均衡等。

分布式无约束优化正如凸优化是集中式优化中的基本问题,无约束分布式凸优化也是分布式优化中最基本的问题和研究的出发点。在无约束优化问题中一个典型而简单的分布式优化问题是分布式凸交计算，通常可以用梯度方法对它进行研究，在它的算法中梯度就是对凸集的投影。

分布式凸交计算这几年,分布式凸交计算(Distributed convex intersec-tion computation)越来越受到研究人员的重视,并在包括图像重构中原像的恢复、凸投射的最佳逼近和目标定位等实际问题中有大量的应用.比如,在目标定位问题中,目标源以一定的功率发射某一信号,网络中的多个传感器会接收到随着传输距离变大而衰减的带量测噪声的信号,目标定位的目的是通过网络中传感器接收到的信号以找到目标源的位置.对应于接收到的信号,每个传感器都会有一个(凸)感知区域.当这些感知区域具有非空交集时,目标定位问题可以转化为一个凸交计算问题.近几十年来,凸交计算问题(也称凸可行性问题)得到广泛的研究.当初的研究通常是集中式的,随后这几年开始了分布式凸交计算的研究。1

次梯度方法(Sub-gradient method)基于次梯度的常步长算法往往不能保证算法的收敛性,或者说即使收敛性能够得到但不能保证一定能收敛到最优解集上.为了保证算法收敛的最优性,步长渐近收敛到 0的条件是必要的,但是该条件又会带来收敛速度慢的弊端。随着分布式优化的深入发展，近些年来，研究人员取得了很多基于(次)梯度的变形算法和研究成果。比如：

a) 基于量化信息的分布式优化。

在基于量化信息的分布式优化这一问题里,每个个体由于通讯能力的限制,不能完全量化得到其他个体的信息,而只能得到通讯量化后的信息.大部分基于次梯度的方法,虽然给出了固定或者切换拓扑下分布式优化的算法的收敛性分析,但是在实际应用中由于量化误差的存在,不能达到精确解,并且其精确程度与量化的精度有关.在该问题中,有一些基本的问题还没有完全解决,特别是:

i)如何实现(在切换拓扑下)不受量化误差影响的精确优化?

ii)如何在能够实现优化的前提下减少信息传输率?

b) 随机优化。2

在一些现实问题中,比如从社会观点动力学的角度而言,个体在做决策时往往会相互独立地以一定的概率坚持自己的观点,以一定概率会受到邻居个体观点的影响。

分布式带约束优化现实中的很多优化问题是带有约束的,其约束形式包括受限集、等式及不等式约束。 同样,在解决分布式优化问题中,也会碰到不少约束问题.实际上,很多非凸的优化问题可以近似为带约束的凸优化问题.

在分布式优化中,有两类约束用在优化算法中.一类是优化问题中不得不考虑的客观给定约束,还有一类是优化问题中自身隐含的约束.对于客观存在的约束,研究者不得不去面对和处理,但在不好处理时就采取方法取代或逼近这些约束条件.而后一类约束往往是所研究的优化问题中自然满足的,有时可以主动加入这些辅助约束以提高算法的效率。