论文部分内容阅读
本文研究如何提高分布式在线算法的收敛速度以及解决非平衡有向切换网络中通信延迟的问题。对于前者,主要基于对拉普拉斯矩阵进行加边,优化网络拓扑以达到增加其代数连通度的目的,从而使分布式在线对偶平均(ODDA)算法和分布式在线无投影(DOCG)算法这两种经典优化算法具有更快的收敛速度。而对于后者,主要通过对通信网络拓扑进行扩维的办法,将通信时延的无约束凸优化问题转化为无时延的无约束凸优化问题,以便于能够高效地解决通信延迟的问题。论文的工作主要包括以下三个部分:第一部分主要通过改进分布式对偶平均算法的办法,使其具有更快的收敛速度。首先将算法扩展到在线设置。然后利用选边方法,每次选出一条最优的边进行加边,并将其加入到网络拓扑中以建立数学模型,从而提出了一种快速分布式在线对偶平均算法(F-ODDA),并证明了 F-ODDA的收敛性,同时给出了收敛速度。最后,理论和数值实验表示,和已有的在线分布式对偶平均算法(ODDA)相比,F-ODDA具有更快的收敛速度。第二部分主要通过改进分布式在线无投影算法的策略,使其具有更好的性能。首先,建立了 Erdos-Renyi(ER)随机模型,并提出了加边扩容算法(AE)。其次,将加边扩容算法与分布式在线无投影算法相结合,提出了一种快速分布式在线无投影算法(F-DOCG)。在保证足够精度的情况下,F-DOCG算法通过线性化的近似避免了高昂的投影计算问题,而且揭示了底层拓扑和代数连通度的联系,同时改进了 Regret界,又能够从理论上保证具有更快的收敛速度。最后,理论和数值实验表示,和已有分布式在线条件梯度算法(DOCG)相比,所提出的F-DOCG具有更快的收敛速度和性能。第三部分主要解决在一般的非平衡有向切换网络中个体间的通信延迟的问题。通过对通信交流网络拓扑进行扩维的办法,将存在通信时延的无约束凸优化问题转变为无时延的无约束凸优化问题,从而提出了基于切换网络下带有时延通信的分布式次梯度优化算法来解决该问题。由于集中考虑了网络拓扑与通信时延,该算法更贴合实际情况。并利用非二次李雅普诺夫函数法在非平衡有向切换网络周期强连通以及通信时延有上界的情况下,证明了基于时延通信的分布式次梯度算法的收敛性。最后,从理论和数值仿真表明了该算法的收敛性和有效性。图[28]表[1]参[69]