分布式优化算法及其隐私保护策略研究

As the interdiscipline of network science and optimization theory, distributed privacy preserving optimization algorithms is a research hot in recent years due to its wide practical applications in resource allocation problems. This project will investigate three classes of distributed optimization algorithms based on the privacy preserving strategies for general interaction graphs including the following three aspects: 1) When the interaction graphs between agents are weight-unbalanced, we will first design the heterogeneous distributed optimization algorithms, and then present the proof that there certainly exist heterogeneous parameters such that the network can achieve a cooperative optimization. Moreover, we also design adaptive learning algorithms guaranteeing the parameters converge to the desired values; 2) We will establish the equivalence between the privacy preserving property of the algorithms and the invertibility of the corresponding input-output systems, and characterize the factors that affect the privacy preserving property based on the results in modern control theory; 3) When the algorithms are not privacy preserving, we will re-design the algorithms based on the obtained results or by virtue of the cryptographic methods guaranteeing that the resulting algorithms are privacy preserving. The methods and theoretical results established in this project are of importance to the operation and management-oriented problems.

由于在资源配置等领域有广泛的应用，分布式隐私保护优化算法是近年来的一个研究热点，也是网络科学和优化理论的交叉研究方向。本项目主要对一般连接图情形下的几种分布式优化算法进行隐私保护设计和分析，研究主要包括以下几个方面：1）当网络连接图是一般的权重非平衡图时，设计分布式异质参数优化算法；给出异质参数的存在性证明；设计出异质参数最优学习适应算法；2）刻画算法的隐私保护性能与其输入输出系统可逆性之间的等价性，进而利用现代控制理论中成熟的结果对影响算法隐私保护性能的因素进行刻画；3）当算法不具有隐私保护性能时，根据得到的影响算法隐私保护性能的系统因素对算法进行重新设计或对算法中个体之间传递的信息进行加密使其具有隐私保护性能。此项目建立的方法和理论必将对运筹管理等问题的解决产生重要的意义。

本项目研究在一般网络图下分布式梯度算法的最优收敛性能以及 隐私保护性能。本项目旨在设计既具有最优收敛性和隐私保护性能的分布式梯度算法。我们得到了以下结果：1)我们深刻刻画了分布式梯度算法在一般网络图下的最优收敛性能，证明了对于任意的联合连通时变网络图，总存在步长使得异质步长算法收敛到最优解；2）我们证明了已有的同步迭代分布式梯度算法在Lebesgue测度下以概率一不是隐私保护的。我们也设计了一个异步迭代分布式梯度算法，此算法不仅可以收敛到最优解，还具有隐私保护性能；3）我们分析了一个连续时间带有投射不确定性的分布式梯度算法的最优收敛性，并建立了保证最优收敛性所需要的投射精度条件；4） 对于一个多方谈判问题，我们设计了一个近似求解Pareto最优解集的具有隐私保护性能的分布式算法。