带量化的分布式Push-sum算法

摘要

考虑了一个由多个个体构成的时变有向网络,网络中每个个体拥有一个仅自己知道的局部目标函数,使得所有个体局部目标函数之总和能够达成最优的分布式优化问题.现实通讯网络中,个体间的通信受带宽限制,本文考虑了个体之间只能交换被量化过后的信息,并结合Push-sum通讯机制和分布式次梯度算法,提出了带量化的分布式Push-sum次梯度算法,并给出收敛分析、收敛速度以及数值实验.　　本文针对带量化的分布式优化问题,提出了确定型量化的分布式Push-sum算法、概率型量化的分布式Push-sum算法、编码器译码器设置的量化的分布式Push-sum算法.　　首先,针对确定型量化的分布式Push-sum算法,需要各个个体之间只能传递和交换确定型量化之后的信息.根据算法本身的更新规则得到该算法是收敛的,同时给出收敛性分析,还用数值实验加以说明.最后得出F((z)i(τ))以速度O(lnτ/τ)收敛到F(z*)还兼有一个与确定型量化精度有关的误差项,确定型量化精度越高,越接近最优.其次,针对概率型量化的分布式Push-sum算法,考虑各个个体之间只能传递和交换概率型量化之后的信息.对收敛性分析也做了分析,最后收敛速度也是O(lnτ/τ),同时兼有一个与概率型量化精度有关的误差项,概率型量化精度越高,越接近最优.对于这两种量化,通过数值实验,证明了量化精度越高,收敛的越快.最后针对编码器译码器设置的量化的分布式Push-sum算法,需要每个个体只能交换和传递编码器译码器设置的量化,再通过理论给出收敛性分析,最终得到每个个体的状态能够收敛到最优解的附近.

目录

1绪论

1.2研究动机以及创新点

1.3本文结构

2预备知识

2.2图与次梯度

2.3 Push-sum优化算法

3确定型量化的分布式Push-sum算法

3.2.2确定量化

3.3确定型量化的Push-sum算法

3.4收敛性分析

3.5数值实验

3.6小结

4概率型量化的分布式Push-sum算法

4.2.2概率量化

4.4收敛性分析

4.5数值实验

5编码器译码器设置的量化的分布式Push-sum算法

5.2.2编码器译码器设置的量化

5.3编码器译码器设置的量化的Push-sum算法

5.4收敛性分析

5.5小结

6结论及展望

参考文献

附录A:作者攻读硕士学位期间发表论文及科研情况

致谢

声明