基于概率量化的分布式无梯度优化算法研究

李德权，陈 平

（安徽理工大学理学院，安徽 淮南232001）

0 引言

近年来，随着网络通讯和计算机科学的飞速发展，人们迎来了大数据、云计算的时代，这导致以往的集总式优化理论已无法适应现在的大规模大数据优化问题［1］。目前，分布式优化理论研究的一类优化问题是：关于整个网络的优化问题可以分解成网络中各个个体目标函数之和，每个个体仅知道其自身目标函数并通过与其邻居个体进行信息交互，从而使整个网络优化问题最优且每个个体状态均在最优解处达到一致。由于不需要考虑网络全局信息及其鲁棒性［2］，因此分布式优化理论最近引起学者们的广泛关注。分布式优化理论主要依赖个体间的局部合作协调从而实现优化任务［3］。文献［4］首先提出了基于多个体一致性的分布式优化问题。

目前，大多数分布式优化问题通常是在假定每个个体目标函数具有梯度或次梯度的前提下进行研究的。但并非所有目标函数（次）梯度均存在或有时（次）梯度需要花费大量复杂而繁琐的计算，因而有学者提出了分布式无梯度优化算法［5］。如文献［6］讨论了随机无梯度的最小值问题，文献［7］讨论了基于push-sum算法的分布式无梯度优化问题，文献［8］讨论了时变网络中的分布式随机无梯度优化问题等等。

此外，随着通信技术的发展，数字通信正逐步取代模拟通信而被广泛应用到各个领域，例如多个体网络的一致性、分布式估计等。由于网络带宽有限，数字通信技术一般通过量化编码将模拟信息转化为数字信息，然后经由数字信号通道进行通讯［9］。信息量化大致可以分为概率量化和确定性量化。概率量化相对于确定性量化具有量化误差的期望为零的优点。但由于随机因素的引入，网络中个体仅能达到概率意义下的收敛［1］。文献［10］首次在切换网络拓扑下讨论了确定性量化对分布式次梯度优化算法的影响。文献［11］则研究了概率量化下分布式算法的平均一致性问题。在文献［11］的基础上，文献［12］进一步讨论了概率量化对分布式次梯度优化算法的影响。

文献［13］主要研究随机投影下分布式优化算法，并应用次梯度算法探究其最优解的收敛情况，而本文在随机投影无梯度优化算法的基础上，考虑概率量化对多个体网络分布式优化算法的收敛性及最优解的影响。

1 问题描述

1．1 基础知识

1．1．1 代数图论

若将网络中每个个体看作是一个节点，则多个体网络中个体间的信息通信可以建模成有向图G＝（v，ε），其中v＝｛v1，v2，…，vM｝，M 为个体数目，边集ε＝v×v用来表示个体间的信息交流过程。若第j个个体是第i个个体的邻居，则有序数对｛j，i｝∈ε，第i个个体的邻居节点的集合记为Ni＝｛j∈v｜（j，i）∈ε｝。

从上述引理可以看出概率均匀量化是无偏差的，但是确定性量化不满足该性质，因而概率均匀量化更适合在平均一致性算法中应用。

1．2 问题的提出

本文考虑的是具有M个个体的网络系统中的分布式优化问题。由于分布式优化所研究的是所有局部目标函数和最小值的问题，因此本文考虑下面这个问题［14］，即：

2 分布式无梯度优化的量化算法

2．1 高斯近似函数

由于本文所要考虑的是一般的目标函数，其不一定有次梯度，或次梯度求解过程太繁琐，所以本文根据参考文献［6］引入高斯近似函数将目标函数fi（x）变为其高斯近似函数：

2．2 量化算法

2．3 相关引理

引理3［6］∀i∈V，L 是函数fi（x）的 Lipschitz约束，则有：

2．4 相关性质

本文将用到的系数矩阵A是双随机矩阵，即满足下列性质［12］：

1）对于∀（i，j）∉ε或i≠j有Aij＝0；

2）A 是对称矩阵即A＝AT且Avec（1）＝vec（1）；

3）ρ（A-（vec（1）vec（1）T）／m）＜1．

其中，vec（1）＝（1，1，…，1）T∈Rm；ρ为矩阵的谱半径。

3 主要结果

定理1 若高斯无梯度预测gi（t）满足引理1且系数矩阵A满足性质3），根据算法（2），对于每个个体i，则有

将以上2个式子相减并同时取范数，并根据高斯无梯度预测gi（t）的有界性得到：

将等式右边第2项展开并根据应用引理1可知

4 结语

本文研究了固定拓扑下多个体网络的目标函数可以分解成网络中每个个体自己知晓的目标函数之和，且个体间通过交互量化信息寻求最优解的问题。研究表明，当概率量化精度足够高且步长足够小时，则所求的解就越接近最优解。

［1］袁德明．多智能体系统的分布式一致与优化［D］．南京：南京理工大学，2012．

［2］Wang Na，Li Dequan，Yin Zhixiang．Broadcast Gossip Algorithm with Quantization．Proceedings of the 9thInternational Conference on Fuzzy Systems and Knowledge Discovery，2012：2157-2161．

［3］洪奕光，张艳琼．分布式优化：算法设计和收敛性分析［J］．控制理论与应用，2014，31（7）．DOI：10．7641／CTA．2014．40 012．

［4］A．Nedic，A．Ozdaglar．Distributed Sub-gradient Methods for Multi-agent Optimization［J］．IEEE Transactions on Automatic Control，2009，54（1）：48-61．

［5］Yu．Nesterov．Random Gradient-free Minimization Functions［J］．CORE Discussion Paper 2011／1．2011．

［6］Y．Nesterov．Random Gradient-free Minimization of Convex Functions［J］．Dept．Center Oper．Res．Econ．，Univ．Catholique de Louvain，Louvain，Belgium，Tech．Rep．，2011／1．

［7］Deming Yuan，Shengyuan Xu，and Jun wei Lu．Gradientfree Method for Distributed Multi-agent Optimization Via push-sum Algorithms［J］．International Journal of Robust and Nonlinear Control，2015，25（10）：1569-1580．

［8］Deming Yuan and DanielW．C．Ho，Randomized Gradient-Free Method for Multi-agent Optimization over Time-Varying Networks［J］．Senior Member，IEEE，2014．

［9］孟诚．二阶多智能体系统一致性研究［M］．控制理论与控制工程，2012．

［10］Nedic A，Olshevsky A．Ozdaglar A，et al．Distributed Subgradient Methods and Quantization Effect［A］．Proceedings of IEEE CDC ［C］，Mexico：IEEE，2008：4177-4184．

［11］Aysal T，Coates M，Rabbat M．Distributed Average Consensus Using Dithered Quantization ［J］．IEEE Transactions on Signal Processing，2008，56（10）：4905-4918．

［12］袁德明，徐盛元，赵环宇，等．分布式多自主体优化问题中的概率量化影响研究［J］．南京理工大学学报：自然科学版，2011，35（2）．

［13］Soomin Lee and Angelia Nedic′．Distributed Random Projection Algorithm for Convex Optimization［J］．Selected Topics in Signal Processing，IEEE．2013，7（2）：221-229．

［14］李婧．基于量化共识的分布式Gossip算法研究［M］．哈尔滨：哈尔滨工业大学出版社，2013．

［15］Xiao L，Boyd S．Fast Linear Iterations for Distributed Averaging［J］．Sys and Contr Letters，2004，53（1）：65-78．