Constrained Consensus and Optimization in Multi-Agent Networks
Constrained Consensus and Optimization in Multi-Agent Networks
复制标题
DOI：
10.1109/tac.2010.2041686
复制
发表时间：
2010-04-01
影响因子：
6.8
通讯作者：
Parrilo, Pablo A.
中科院分区：
文献类型：
--
作者：
Nedic, Angelia;Ozdaglar, Asuman;Parrilo, Pablo A.
我们提出了分布式算法，可以由多个代理使用，以使他们的估计与时变连接网络上的特定值保持一致。我们的框架是通用的，因为这个值可以表示多个智能体之间的共识值或优化问题的最优解，其中全局目标函数是局部智能体目标函数的组合。针对每个智能体的估计被限制在不同的凸集上的约束问题，我们首先考虑了一个受约束的一致性问题，提出了一种分布式的“投影一致性算法”，该算法将智能体的局部平均运算与各自约束集上的投影相结合。该算法可以被视为交替投影法的一个版本，其权重随着时间和不同的代理而变化。我们建立了投影一致性算法的收敛和收敛速度结果。接下来，我们研究了一个约束优化问题，该问题是在主体的局部约束集相交的情况下，对主体的局部目标函数之和进行优化。我们提出了一种分布式的“投影次梯度算法”，每个代理执行一个局部平均操作，采取一个次梯度步骤最小化自己的目标函数，然后投影到它的约束集上。我们证明了，在适当选择步长规则的情况下，当权重恒定且相等时，以及当权重时变但所有代理具有相同的约束集时，该算法所生成的代理估计收敛于相同的最优解。
We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets.To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed "projected consensus algorithm" in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed "projected subgradient algorithm" which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set.