具有通信时延的多个体分布式凸优化算法研究

摘要

多个体系统在生物、人工智能和协调控制等具有广泛的应用，多个体分布式凸优化算法就是利用多个体之间的相互协作来解决凸优化问题。而在实际中，通信时延对于多个体系统的作用不可忽视，它可能会延缓多个体系统达到一致状态的速度，从而降低多个体系统运行的效率，因此研究具有通信时延的多个体分布式优化问题具有十分重要的意义。本文主要研究存在固定通信时延的分布式次梯度优化算法，分析通信时延对算法性能的影响。主要工作分为以下两个方面:
　　一、固定拓扑时延分布式次梯度优化算法的研究。关于多个体系统的分布式次梯度优化算法已有相当的研究。本文在此基础上考虑了时延这一重要因素。在存在通信时延情况下，通过系统扩维将时延优化问题转化为无时延优化问题来处理，这样使得描述网络拓扑的权矩阵被替换成了时延矩阵。然而即使权矩阵是双随机矩阵，时延矩阵也不再是双随机的，而是一个随机矩阵，这使算法收敛性分析变得非常困难。双随机矩阵有很好的收敛性质，其每个元素都将最终收敛到平均值。但系统扩维后新增的时延个体只转播信息而不参与迭代运算，因而个体的重要性不再相同，因而时延矩阵是一个随机矩阵。本文利用随机矩阵与其平稳分布的关系，从理论上证明了分布式时延次梯度算法的收敛性。最后，通过仿真算例进一步验证了算法的有效性。
　　二、切换拓扑时延分布式次梯度投影算法的研究。考虑了个体状态具有凸约束限制的优化问题;同时，所考虑的网络拓扑结构不再是固定不变，而是随时间变化的动态切换拓扑。针对时延，仍然采用系统扩维的方法来解决;针对个体状态凸约束限制，则引入投影运算。由于动态切换的拓扑结构的关系，此时的时延矩阵不仅仅只是一个随机矩阵，而且还是一个随时间变化的动态矩阵。上述关于固定拓扑时延矩阵的收敛性质在这种情况下不再适用。本文利用随机转移矩阵依几何速度收敛到行相同随机矩阵的性质，证明了所提算法的收敛性。
　　总之，在网络强连通（固定拓扑）或周期强连通（切换拓扑），以及通信时延有界条件下，所提出的算法是收敛的。亦即时延并不改变算法的收敛性，但影响算法的收敛性能。从算法的理论分析和仿真结果可知，通信时延的存在将使得算法的收敛速度变慢，收敛误差变大。

目录

声明

摘要

符号说明

引言

1 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 本文的主要内容及结构

2 预备知识

2．1 凸优化

2．2 次梯度

2．3 图与矩阵

2．4 投影

2．5 次梯度算法

3 固定拓扑分布式时延次梯度算法

3．1 时延模型

3．2 系统扩维

3．3 时延次梯度算法及其收敛性

3．4 仿真实验

3．5 结论

4 切换拓扑时延次梯度投影算法

4．1 分布式次梯度投影算法

4．2 分布式时延次梯度投影算法

4．3 结论

结束语与展望

参考文献

致谢

作者简介及读研期间主要科研成果