Source-linked AI summary
Constrained Consensus
Angelia Nedić, Asuman Ozdaglar, Pablo A. Parrilo
TL;DR
The paper addresses distributed consensus and optimization when each agent’s estimate must remain in a locally known constraint set. It proposes projected consensus and projected subgradient algorithms, establishing convergence under specified connectivity, weighting, and constraint-set regimes. The results include consensus in the intersection of local sets and convergence to an optimal constrained solution.
Problem
Distributed consensus and optimization need algorithms for settings where agent estimates are constrained to locally known, potentially different sets.
Method
The paper combines local averaging with projection for consensus, and adds local subgradient steps before projection for constrained optimization.
Results
The projected consensus estimates converge to a common point in the constraint intersection, while projected subgradient estimates converge to a common optimum under specified regimes.
Takeaways & Limitations
Constraints can be handled with distributed projected updates even when each agent knows only its own constraint set.
Takeaways & Limitations
The optimization convergence results cover same constraints with time-varying weights or different constraints with time-invariant uniform weights, and extensions require suitable error bounds.
Abstract
from arXiv · showhide
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 estimate of each agent is restricted to lie in a different constraint set. 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.
1 Introduction
The paper develops distributed algorithms for consensus and optimization when agents’ estimates must satisfy locally known constraints. It analyzes projected consensus and projected subgradient methods under time-varying networks and selected constraint or weighting regimes.
- Motivation: Existing distributed consensus and optimization work largely does not address agent values constrained to distinct sets.Such constraints arise in applications including motion planning, alignment, and constrained multi-agent optimization.
- Constrained consensus: The projected consensus algorithm averages values from time-varying neighbors and projects the result onto each agent’s local constraint set.The update is interpreted as an alternating projection method with weights varying across time and agents.
- Analysis: The convergence analysis decomposes nonlinear projected dynamics into time-varying linear averaging and nonlinear projection-error components.This separates constraint effects from the convergence analysis of local averaging.
- Constrained optimization: The projected subgradient algorithm combines local averaging, a subgradient step for each local objective, and projection onto the local constraint set.It targets a global objective formed by summing local objectives over the intersection of local constraint sets.
- Constrained optimization: With an appropriately selected stepsize, agent estimates converge to the same optimal solution when constraint sets are identical with time-varying connectivity or distinct with uniform constant weights.The distinct-set case uses an error bound relating distances to individual sets and their intersection.
- Related work: The work builds on distributed optimization and consensus literature while focusing on settings where constraint information is distributed across agents.Earlier related approaches considered unconstrained optimization or constraint sets known by all agents.
2 Notation, Terminology, and Basics
This section establishes notation for vectors, stochastic weights, distances, projections, and closed convex sets. It then states projection properties and an interior-point-based error-bound framework used in later convergence analysis.
- Notation: Vectors are treated as columns, with component notation x_i or [x]_i, transpose x′, scalar product x′y, and Euclidean norm ∥x∥.
- Weights: A stochastic vector has nonnegative components summing to one, while a doubly stochastic matrix has stochastic rows and columns.
- Projection notation: dist(x̄, X) denotes Euclidean distance to a set, and P_X[x̄] denotes projection onto a closed convex set.
- Projection properties: Projection on a closed convex set satisfies a projection inequality and a non-expansiveness property used in subsequent analysis.The section introduces these properties before stating additional projection lemmas.
- Projection lemmas: For y in a nonempty closed convex set X, projection satisfies ∥P_X[x]−y∥^2 ≤ ∥x−y∥^2−∥P_X[x]−x∥^2.This relates distance after projection to the projection error.
- Error bounds: Under an interior-point assumption on the intersection of closed convex sets, an error bound relates an averaged vector’s distance to the intersection and its distances to the individual sets.The paper uses this relation in analyzing projection errors and convergence.
3 Constrained Consensus
The constrained consensus algorithm combines time-varying weighted averaging with projection onto each agent’s local closed convex constraint set. Under the stated assumptions, agents converge to a common feasible point, with geometric convergence established for constant uniform weights under an interior-point assumption.
- Algorithm: Each agent forms a weighted combination of neighboring estimates and projects the result onto its own constraint set Xi.The update is locally executed and can be interpreted as weighted alternating projection with weights varying across agents and time.
- Algorithm: The projected consensus update is also interpretable as distributed gradient descent on fi(x) = 1/2 ∥x − PXi[x]∥2.The projection residual is the negative-gradient step with stepsize 1 after local averaging.
- Scope: If the constraint intersection is empty, the agent estimates do not reach consensus and may oscillate or become unbounded.The paper explicitly focuses its convergence analysis on a nonempty intersection.
- Convergence: The projection errors converge to zero, and the projected and pre-projection iterates asymptotically approach one another.The analysis also shows lim k→∞∥xi(k) − y(k)∥ = 0 and lim k→∞∥wi(k) − y(k)∥ = 0 for all agents.
- Convergence: If the constraint intersection is nonempty and the model assumptions hold, all agent estimates converge to the same point in the intersection.The analysis establishes lim k→∞∥xi(k) − x̃∥ = 0 for every agent, along with convergence of the intermediate weighted iterates.
- Convergence Rate: Under constant uniform weights and an interior-point assumption, the projected consensus algorithm converges at a geometric rate.This setting corresponds to a fixed, fully connected communication graph.
4 Constrained Optimization
The paper formulates constrained distributed optimization over time-varying networks and introduces a projected subgradient method combining consensus, local subgradient steps, and local projections. Under selected conditions, all agent estimates converge to a common optimal solution in two network–constraint settings.
- Problem: The agents minimize a sum of convex local objectives over the intersection of their closed convex local constraint sets, with each agent knowing only its own objective and constraint set.The local functions need not be differentiable; subgradients handle nondifferentiable points.
- Algorithm: Each agent averages received estimates, takes a subgradient step for its local objective, and projects the result onto its local constraint set.The projected subgradient algorithm is rewritten to separate linear mixing effects from nonlinear subgradient and projection effects.
- Analysis: The convergence analysis studies the nonlinear iterates through auxiliary sequences and transition matrices, tracking consensus disagreement and projection-induced errors.The analysis uses bounded subgradients, stepsize conditions, and convolution bounds for vanishing error terms.
- Convergence when Xi = X: When all constraint sets are identical and connectivity is time-varying, the agent estimates converge to the same optimal point under the stated assumptions and stepsize conditions.The iterates asymptotically approach an auxiliary sequence and then converge to some x* in the optimal set X*.
- Convergence for uniform weights: With different constraint sets and uniform constant weights, the agent estimates also converge to a common optimal solution under the corresponding assumptions and stepsize conditions.Uniform weights correspond to a fully connected communication graph in each step.
5 Conclusions
The paper establishes convergence results for projected consensus and projected subgradient algorithms under specified network, weight, constraint, and stepsize conditions. It also identifies extensions to broader constraint and weighting settings as future work.
- Projected consensus estimates converge to a common limit in the intersection of the agents’ closed convex constraint sets under assumptions on weights and network connectivity.
- Geometric convergence holds for projected consensus under an interior point assumption when agent weights are time-invariant and uniform.
- The projected subgradient algorithm converges to an optimal solution when stepsizes decrease sufficiently fast, for equal constraint sets or time-invariant uniform weights with different sets.
- A proposed research direction is extending constrained optimization to include global constraints, potentially using primal-dual subgradient algorithms.
- The paper leaves convergence analysis for different constraint sets with general time-varying weights to future work, pending a suitable error bound.