Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication
Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication
复制标题
DOI：
10.1016/j.automatica.2015.03.001
复制
发表时间：
2015-05-01
期刊：
影响因子：
6.4
通讯作者：
Martinez, Sonia
中科院分区：
文献类型：
--
作者：
Kia, Solmaz S.;Cortes, Jorge;Martinez, Sonia
本文提出了一类新型分布式连续时间协调算法，用于解决成本函数是与单个代理相关的局部成本函数之和的网络优化问题。我们确定了所提算法在以下情况下的指数收敛性：(i) 局部成本为强凸且具有全局 Lipschitz 梯度的强连接和权重平衡数字图拓扑；(ii) 局部成本为强凸且具有局部 Lipschitz 梯度的连接图拓扑。当局部成本函数为凸函数且全局成本函数为严格凸函数时，我们会在连通图拓扑下建立渐近收敛性。我们还描述了该算法在时变交互拓扑下的正确性，并研究了其隐私保护特性。出于实际考虑，我们分析了离散时间通信的算法实现。我们提供了一个步长上界，它能保证在有周期性通信的实现中，在连通图上呈指数收敛。在这一结果的基础上，我们设计了一种可证明正确的集中式事件触发通信方案，该方案不存在 Zeno 行为。最后，我们还开发了一种分布式异步事件触发通信方案，该方案也不存在 Zeno，并能保证渐近收敛。我们的结果可通过几个模拟来说明。(C) 2015 爱思唯尔有限公司。保留所有权利。
This paper proposes a novel class of distributed continuous-time coordination algorithms to solve network optimization problems whose cost function is a sum of local cost functions associated to the individual agents. We establish the exponential convergence of the proposed algorithm under (i) strongly connected and weight-balanced digraph topologies when the local costs are strongly convex with globally Lipschitz gradients, and (ii) connected graph topologies when the local costs are strongly convex with locally Lipschitz gradients. When the local cost functions are convex and the global cost function is strictly convex, we establish asymptotic convergence under connected graph topologies. We also characterize the algorithm's correctness under time-varying interaction topologies and study its privacy preservation properties. Motivated by practical considerations, we analyze the algorithm implementation with discrete-time communication. We provide an upper bound on the stepsize that guarantees exponential convergence over connected graphs for implementations with periodic communication. Building on this result, we design a provably-correct centralized event-triggered communication scheme that is free of Zeno behavior. Finally, we develop a distributed, asynchronous event-triggered communication scheme that is also free of Zeno with asymptotic convergence guarantees. Several simulations illustrate our results. (C) 2015 Elsevier Ltd. All rights reserved.