网络化的并行与分布式优化算法研究及应用

摘要

传统的信息处理系统由采集-传输-处理-反馈控制四大分立过程组成，其中前端传感器采集的数据通过网络汇总至数据中心进行集中处理，数据中心通过网络往前端执行部件发布控制命令。这样的模式存在网络容量受限、链路反馈延时长和系统鲁棒性差等三大缺陷。
　　网络化处理是将采集-传输-处理-反馈控制融合于网络之中，网络既是数据来源和存储载体，又是信息传输、处理和反馈控制的执行者。这样的模式可以有效克服上述的三大缺陷。在网络化处理中，最优化问题受到广泛关注。一方面，信号处理、模式识别、机器学习和通信理论等多个领域的问题都可表示为最优化形式。另一方面，网络中对于节点协作、传输形式、能量约束等物理要求可以自然地建模为最优化形式。
　　本文主要研究网络化的并行与分布式优化算法。其中一方面，要对优化目标进行并行或分布式解耦以替代传统的集中式处理。另一方面，必须考虑网络的实际拓扑，需要设计特定的信息交互方式以减少计算过程中的通信开销。
　　本文的理论基础来源于经典优化理论，在第2章中介绍了无约束和有约束优化问题的一般性解法，并对并行和分布式解耦的一般性方法进行了总结。第2章中还证明了无约束和有约束形式在某些情况下存在等价转换，这种转换更利于优化问题的并行和分布式解耦。
　　以节点间通信方式划分，网络化的优化算法可以分为局部融合、接力传递和局部广播三大类。第一类的现有算法针对优化变量大都采取单一处理方式，但在并行和分布式解耦过程中可能引入优化难度不同的多变量。鉴于这种情况，第3章和第4章对多变量选择不同的处理函数，构成交替计算的同步快速优化算法。其中，第3章的算法处理的是一般形式的双变量目标函数，第4章则进一步考虑了带局部可行域的不可导凸函数。这两章的算法中节点间通信采用局部融合的方式，避免了全局的信息交互，降低了通信复杂度。仿真结果表明，相比采用单一处理方式的现有算法，所提算法在计算复杂度和通信复杂度两方面都有优势。
　　同步的局部融合中，每个节点变量更新都需要获取网络中邻居的数据，这伴随着较大的通信开销。因此，在第5章中引入近年发展起来的增量次梯度算法，以实现接力式的分布式优化。通过应用于分布式信号估计的仿真，表明该方式比现有基于局部融合的优化算法要更节省通信开销。
　　为了在降低通信开销的同时，进一步提高计算并行度，在第6章中提出基于随机广播的分布式优化算法。其中，每个节点按照一定概率随机广播自己的数据，成功接收到的节点进行局部计算。在此过程中，还考虑了网络中的传输碰撞。
　　本文中的算法都给出了应用示例，但这些算法并不是针对某些特殊问题提出的，完全可以运用到其他网络优化的场景中去。作为对未来延续的展望，本文的算法可以结合网络中的传输延时，拓扑变动，量化传输等内容进行讨论。

目录

摘要

第1章 绪论

1．1 研究背景和目的

1．2 系统框架和问题描述

1．3 研究历史和现状

1．3．1 经典最优化流派

1．3．2 群体智能流派

1．4 本文的主要工作和内容组织

第2章 并行和分布式优化的理论基础

2．1 无约束优化问题

2．1．1 下降法

2．1．2 下降方向

2．1．3 步长规则

2．1．4 收敛性

2．2 有约束优化问题

2．2．1 可行域的引入

2．2．2 投影法

2．2．3 对偶理论

2．2．4 等式约束的乘子法

2．2．5 不等式约束的内点法

2．3 并行和分布式最优化

2．3．1 G-S方法

2．3．2 SOP方法

2．3．3 并行乘子法

2．3．4 分布式乘子法

2．4 无约束和有约束优化问题的等价变换

2．5 小结

第3章 可导目标函数的分化乘子法

3．1 乘子法的局限

3．2 分化乘子法SMoM

3．3 SMoM算法的并行和分布式推广

3．4 SMoM算法的收敛性分析

3．5 SMoM算法在Logistic回归上的应用

3．5．1 并行式Logistic回归

3．5．2 分布式Logistic回归

3．6 小结

第4章 不可导目标函数的混合乘子法

4．1 交替方向乘子法ADMoM及其局限

4．2 混合优化算法HMoM

4．3 HMoM算法的并行和分布式推广

4．4 HMoM算法的收敛性分析

4．5 HMoM在稀疏信号恢复中的应用

4．5．1 并行式稀疏信号恢复

4．5．2 分布式稀疏信号恢复

4．6 小结

第5章 基于增量次梯度的分布式信号估计

5．1 增量次梯度投影算法IS

5．1．1 接力模式

5．1．2 步长规则

5．2 IS算法的收敛性

5．2．1 轮转顺序

5．2．2 随机顺序

5．2．3 马尔科夫顺序

5．3 IS算法于分布式信号估计中的应用

5．3．1 分布式最大似然估计DIS-MLE

5．3．2 分布式最优线性无偏估计DIS-BLUE

5．3．3 分布式最小二乘估计DIS-LSE

5．3．4 分布式最大后验概率估计DIS-MAP

5．3．5 分布式最小均方误差估计DIS-LMMSE

5．4 仿真对比与分析

5．4．1 分布式MLE算法

5．4．2 分布式BLUE算法

5．4．3 分布式MAP算法

5．4．4 分布式LMMSE算法

5．5 小结

第6章 利用随机广播的无偏一致性和分布式优化算法

6．1 网络一致性算法与Gossip算法

6．2 算法描述

6．3 收敛性分析

6．3．1 C-RBG的收敛性

6．3．2 DGD-RBG的收敛性

6．4 仿真结果与分析

6．4．1 C-RBG算法

6．4．2 DGD-RBG算法

6．5 小结

第7章 总结与展望

7．1 全文总结

7．2 工作展望

参考文献

已发表或录用论文列表

已申请专利列表

致谢

声明