论文标题
原始方法能否优于分散动态优化的原始二重要方法？
Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
论文作者
论文摘要
在本文中，我们考虑了通过多代理网络定义的分散动态优化问题。每个代理都具有随时间变化的本地目标函数，所有代理旨在协作跟踪漂流的全局最佳解决方案，以最大程度地减少所有局部目标函数的总和。分散的动态优化问题可以通过原始或原始偶的方法来解决，当问题退化为静态时，在文献中已经证明了原始偶的方法优于原始方法。这促使我们提出：原始偶的方法是否一定比分散动态优化的原始方法更好？ 为了回答这个问题，我们研究并比较了原始方法，扩散和原始双重方法，分散梯度跟踪（DGT）的收敛性能。理论分析表明，在某些动态设置中，扩散可以胜过DGT。我们发现，DGT和扩散分别受最佳梯度的漂移和大小的显着影响。此外，我们表明DGT对网络拓扑更敏感，并且连接不良的网络可以极大地恶化其收敛性能。这些结论提供了有关如何在各种应用程序方案中选择适当动态算法的指南。构建数值实验以验证理论分析。
In this paper, we consider the decentralized dynamic optimization problem defined over a multi-agent network. Each agent possesses a time-varying local objective function, and all agents aim to collaboratively track the drifting global optimal solution that minimizes the summation of all local objective functions. The decentralized dynamic optimization problem can be solved by primal or primal-dual methods, and when the problem degenerates to be static, it has been proved in literature that primal-dual methods are superior to primal ones. This motivates us to ask: are primal-dual methods necessarily better than primal ones in decentralized dynamic optimization? To answer this question, we investigate and compare convergence properties of the primal method, diffusion, and the primal-dual approach, decentralized gradient tracking (DGT). Theoretical analysis reveals that diffusion can outperform DGT in certain dynamic settings. We find that DGT and diffusion are significantly affected by the drifts and the magnitudes of optimal gradients, respectively. In addition, we show that DGT is more sensitive to the network topology, and a badly-connected network can greatly deteriorate its convergence performance. These conclusions provide guidelines on how to choose proper dynamic algorithms in various application scenarios. Numerical experiments are constructed to validate the theoretical analysis.
