Source-linked AI summary
Consensus optimization on manifolds
Alain Sarlette, Rodolphe Sepulchre
TL;DR
The paper studies distributed synchronization and balancing for agents on connected compact homogeneous manifolds without external references. It defines an embedding-based induced arithmetic mean and derives gradient consensus algorithms, including adaptations for directed and time-varying graphs. SO(n), Grass(p,n), and circle examples illustrate the framework, while convergence for the varying directed algorithms remains mostly open except with estimator variables.
Problem
Distributed synchronization and balancing are well understood in Euclidean spaces, but global versions on compact non-Euclidean manifolds are less broadly covered beyond the circle.
Method
The paper embeds the manifold in Euclidean space, defines consensus through extrema of a cost function linked to the induced arithmetic mean, and derives gradient algorithms using relative agent states.
Results
The framework is illustrated on SO(n), Grass(p,n), and the circle, with algorithms for fixed undirected graphs and estimator-based convergence results for directed and time-varying graphs.
Takeaways & Limitations
The induced arithmetic mean is easily computable in closed form for important manifolds and provides a common basis for synchronization and balancing algorithms.
Takeaways & Limitations
For varying graphs, the direct algorithms can enter limit cycles, and convergence properties are mostly open; the estimator-based approach establishes convergence only to complete-graph anti-consensus or consensus states.
Abstract
from arXiv · showhide
The present paper considers distributed consensus algorithms that involve N agents evolving on a connected compact homogeneous manifold. The agents track no external reference and communicate their relative state according to a communication graph. The consensus problem is formulated in terms of the extrema of a cost function. This leads to efficient gradient algorithms to synchronize (i.e. maximizing the consensus) or balance (i.e. minimizing the consensus) the agents; a convenient adaptation of the gradient algorithms is used when the communication graph is directed and time-varying. The cost function is linked to a specific centroid definition on manifolds, introduced here as the induced arithmetic mean, that is easily computable in closed form and may be of independent interest for a number of manifolds. The special orthogonal group SO(n) and the Grassmann manifold Gr(p,n) are treated as original examples. A link is also drawn with the many existing results on the circle.
1 Introduction
The paper addresses distributed synchronization and balancing for agents evolving on connected compact homogeneous manifolds, where Euclidean consensus tools do not directly apply. It proposes a relative-state, optimization-based framework illustrated on SO(n), Grass(p,n), and the circle.
- Motivation: Synchronization drives agents to a common state, while balancing spreads them across the available state space.These tasks arise in swarm operation, distributed decision making, networks, clustering, and covering.
- Problem: Many applications involve non-Euclidean manifolds, including orientations evolving on SO(2) or SO(3), while balancing requires compact state spaces.Global synchronization and balancing on general manifolds were described as less studied than the corresponding circle problem.
- Framework: The framework treats consensus on connected compact homogeneous manifolds, whose symmetry makes relative agent configurations central.A homogeneous manifold is represented as a quotient of two Lie groups, with all points treated equivalently.
- Method: The method embeds the manifold in Euclidean space and constructs a cost function from distances between agents in that embedding.The associated centroid is studied as the induced arithmetic mean.
- Examples and context: SO(n), Grass(p,n), and S1 provide the principal examples linking the framework to attitude synchronization, subspace states, and existing circle results.Other possible targets include spheres and connected compact Lie groups.
- Algorithms: Gradient algorithms use only relative positions and prove convergence for fixed connected undirected graphs.The paper also develops adaptations for directed and time-varying communication graphs.
2 Preliminaries
The preliminaries define weighted directed communication graphs, connectivity conditions for time-varying links, and the manifold representations used in the paper. SO(n) and Grass(p,n) are connected, compact homogeneous state spaces with distinct matrix descriptions.
- Communication graphs: A weighted digraph represents agents as vertices and communication links as directed edges carrying positive weights.The edge j ⇝ k means agent j sends information to agent k.
- Communication graphs: Vertex out-degree measures sent information, while in-degree measures information received from other agents.These quantities form diagonal out-degree and in-degree matrices.
- Communication graphs: Balanced graphs have equal in-degree and out-degree matrices, and undirected graphs satisfy this condition.Bidirectionality requires reciprocal edges but does not require a symmetric weight matrix.
- Communication graphs: The Laplacian is L = D−A, with directed in- and out-Laplacians determined by the chosen degree matrix.The in-Laplacian has zero column sums and the out-Laplacian has zero row sums.
- Connectivity: A directed graph is strongly connected when every vertex reaches every other by a directed path, and weakly connected when this holds after ignoring direction.Time-varying graphs use the same definitions at each time.
- Connectivity: Uniform connectivity for a δ-digraph requires one vertex to reach all others across every time window of a fixed horizon.The δ condition prevents nonzero edge weights from vanishing below a fixed threshold.
- Specific manifolds: SO(n) is the compact connected homogeneous manifold of positively oriented orthonormal bases, equivalently rotation matrices, with dimension n(n−1)/2.It is the natural state space for rigid-body orientations.
- Specific manifolds: Grass(p,n) represents p-dimensional subspaces of Rn and has dimension p(n−p), with complementary-subspace symmetry.Its projector representation is non-unique in basis form but provides an embedding used by the framework.
3 The induced arithmetic mean
The induced arithmetic mean defines manifold centroids through Euclidean embedding distances, yielding computationally tractable consensus representatives. Closed-form characterizations are given for the circle, SO(n), and Grass(p,n), with multiplicity determining when the mean is unique.
- Definition: The induced arithmetic mean IAM is the set of manifold points minimizing weighted squared Euclidean distances to the agents.The anti-IAM instead maximizes the same weighted distance sum.
- Definition: Unlike the Karcher mean, the IAM uses distances in the embedding space rather than geodesic distances on the manifold.This distinction gives the IAM a different geometric construction.
- Properties: The IAM is single-point exact, invariant under equal-weight permutations, and commutes with the manifold’s symmetry group.It does not always reduce to a single point, a property also associated with other means satisfying the stated properties.
- Computation: Computing the IAM reduces to finding global maximizers of a linear function over the embedded manifold.For SO(n), Grass(p,n), and spheres, local maximization suffices under the stated no-spurious-local-maxima property.
- Examples: On the circle, the IAM is the central projection of the centroid, using chordal distance instead of the Karcher mean’s arclength distance.A zero centroid makes the IAM the whole circle; otherwise it is a single point.
- Special orthogonal group: For SO(n), the IAM is linked to the polar decomposition of the Euclidean centroid and has a closed-form characterization based on its determinant and eigenvalue multiplicities.When det(Ce) ≥0, the IAM consists of positive-determinant polar factors; uniqueness depends on the multiplicity of zero eigenvalues.
- Grassmann manifold: For Grass(p,n), the IAM contains all dominant p-eigenspaces of the centroid projector and is unique when the p-largest and (p+1)-largest eigenvalues differ.The associated objective is a generalized Rayleigh quotient, and the geometric cost minimizes squared sines of principal angles.
4 Consensus
Consensus is defined through the induced arithmetic mean of neighbors, while anti-consensus uses the induced arithmetic anti-mean. Complete graphs reduce consensus to synchronization, whereas balancing and anti-consensus can have broader, graph- and manifold-dependent behavior.
- Definitions: Consensus places each agent at the induced arithmetic mean of its graph-defined neighbors; anti-consensus replaces that mean with the induced arithmetic anti-mean.The definition is graph-dependent because each agent evaluates only the neighbors connected through incoming edges.
- Complete graphs: For an equally weighted complete graph, the only possible consensus configuration is synchronization, where all agents occupy one common point.The paper identifies synchronization as a configuration of complete consensus.
- Balancing: Balanced configurations require the induced arithmetic mean to contain the entire manifold, but they need not exist, are generally non-unique, and require sufficiently many agents.The minimum number of agents is not straightforward to determine on the Grassmann manifold, and analogous existence claims for SO(n) are supported only by simulations.
- Balancing: All balanced configurations are anti-consensus configurations for the equally weighted complete graph, but the converse fails because exceptional anti-consensus configurations may be unbalanced.Thus anti-consensus is a broader condition than balancing in this setting.
- Circle examples: On ring graphs, multiple qualitatively different consensus and anti-consensus configurations occur, including graph-dependent equivalences and degenerate states that are simultaneously both.For example, seven agents spaced by 2π/7 and 4π/7 occupy equivalent position sets when the graph assignment is discarded.
5 Consensus optimization strategy
The paper formulates consensus and anti-consensus as extrema of a graph-based cost function on a manifold. Under the stated assumptions, optimizing this cost certifies local consensus or anti-consensus, although it need not capture every such configuration.
- Cost function: The cost function PL is constructed from graph couplings so that its extrema represent synchronization or balancing-related consensus configurations.Its quadratic-form representation connects the objective to the graph Laplacian.
- Circle connection: On the circle, the complete-graph objective is proportional to the squared norm of the centroid and matches the classical complex order parameter.Earlier work used the same objective to derive synchronization and balancing gradient algorithms.
- Optimization properties: Synchronization is the unique global maximum of PL whenever the associated graph is weakly connected.Equality of connected agents propagates through a weakly connected graph, forcing all agents to coincide.
- Optimization properties: A local maximum of PL necessarily corresponds to consensus, while a local minimum necessarily corresponds to anti-consensus under the manifold assumptions.This establishes sufficiency of optimization for identifying these configurations.
- Limitation: Optimizing PL is sufficient but not necessary for all anti-consensus configurations, because it tests one-agent motions with the others fixed rather than coordinated multi-agent directions.For a tree, maximizing PL always produces synchronization even though other consensus configurations can exist.
6 Gradient consensus algorithms
The paper derives gradient ascent and descent algorithms from PL using the embedding-induced manifold gradient, then extends the update to directed and time-varying graphs. Fixed undirected graphs converge to equilibria with stable consensus or anti-consensus determined by the sign of the gain.
- Gradient design: The algorithms use continuous-time ascent or descent of PL, with gradients defined by the canonical metric induced by the manifold embedding.Discrete-time ascent and descent methods can target the same optimization tasks.
- Gradient design: Each agent implements the update by projecting the ambient gradient onto its manifold tangent space using relative positions of connected agents.For directed graphs, the basic gradient implementation requires information from both incoming and outgoing links, so the direct form is restricted to undirected graphs.
- Fixed undirected graphs: For undirected graphs, all trajectories converge to equilibria; stable equilibria are consensus for α > 0 and anti-consensus for α < 0.For an equally weighted complete graph, synchronization is the only asymptotically stable configuration.
- Directed and time-varying graphs: With directed and time-varying graphs, the gradient interpretation is lost, but synchronization remains stable and becomes asymptotically stable when disconnected graph sequences are excluded.Its basin includes configurations contained in a convex subset of the manifold.
- Limitations and examples: Varying graphs can produce limit cycles, demonstrated by switching between ring graphs where the same state alternates between a local maximum and a local minimum of PL.Simulations on randomly generated digraph sequences suggest eventual synchronization, but this is reported as an indication rather than a proof.
- Manifold examples: On SO(n) and Grass(p,n), the paper verifies the manifold assumption needed for the optimization results and gives explicit tangent-space gradient constructions.For Grassmann manifolds, local maxima of the relevant linear function correspond to eigenspaces associated with the largest eigenvalues.
7 Consensus algorithms with estimator variables
Estimator variables let agents use weak, directed, and time-varying communication graphs while theoretically retaining synchronization or anti-consensus behavior. The synchronization scheme converges to a common projected state, and the anti-consensus scheme converges to an equilibrium of the complete-graph anti-consensus dynamics.
- Estimator-based communication: Estimator variables compensate for reduced communication by enabling synchronization or balancing relative to the equally-weighted complete graph under weak communication conditions.Interconnected agents communicate x_k in R^m, while each geometric state y_k remains on M.
- Synchronization algorithm: The estimator dynamics are a classical consensus algorithm in R^m, with exponentially convergent x_k under piecewise-continuous, uniformly connected graphs.For balanced graphs, the common limit x_infty equals the centroid of the initial estimator values.
- Synchronization algorithm: The only stable limit configuration of the estimator-projection scheme is synchronization at y_infty = Proj^T_M,k(x_infty); balanced graphs additionally yield y_infty = IAMg{x_k(0)}.The result assumes a piecewise-continuous, uniformly connected graph and a manifold satisfying Assumptions 1 and 2.
- Synchronization algorithm: Gradient ascent has synchronization as its only stable situation once all estimator variables converge to x_infty.The proof uses stability of unique maximizers and identifies the chain recurrent set with critical points.
- Implementation: The variables x_k and y_k must remain fully coupled in discrete-time implementations, requiring implicit update equations to preserve convergence.The continuous-time construction couples estimator evolution in R^m with geometric motion on M.
- Anti-consensus algorithm: With x_k(0) = y_k(0), the anti-consensus estimator scheme converges to an equilibrium of the equally-weighted complete-graph anti-consensus algorithm.This is established for piecewise-continuous, uniformly connected, balanced graphs; simulations generically show convergence to an anti-consensus configuration.
8 Conclusion
The paper introduces a computable induced arithmetic mean, extends consensus and balancing to connected compact homogeneous manifolds, and designs distributed optimization-based algorithms. Its estimator-variable construction establishes convergence under directed and time-varying graphs, while communication of estimators remains unresolved for some manifolds.
- Contributions: The induced arithmetic mean defines a computable centroid for embedded connected compact homogeneous manifolds and differs from the traditional Karcher mean.Analytical solutions are provided for SO(n) and Grass(p,n).
- Contributions: Consensus is linked to the induced arithmetic mean, extending circle balancing to connected compact homogeneous manifolds.For the equally-weighted complete graph, consensus is equivalent to synchronization; anti-consensus appears to yield balancing when N is sufficiently large, but this is unproved.
- Contributions: Optimization-based distributed algorithms are derived for fixed undirected graphs, while estimator-variable modifications establish convergence to complete-graph (anti-)consensus under directed and time-varying graphs.For the basic directed or varying-graph algorithms, convergence properties are mostly open.
- Open issue: Meaningful communication of estimator variables remains an open issue when the manifold is not a subgroup of SO(n).This limits how the estimator-based algorithms can be implemented while preserving swarm autonomy.
- Examples and connections: SO(n) and Grass(p,n) provide running examples, and the resulting circle models and results are strictly equivalent to existing work.The circle connection links the framework to established synchronization and balancing literature.
9 Appendix
The appendix characterizes stationary points of a matrix equation on SO(n) using a polar decomposition and an eigenbasis of its symmetric factor. The resulting orthogonal matrices are diagonal sign choices constrained by determinant compatibility.
- Stationary-point characterization: The equation g(Q) = Q^T B − B^T Q = 0 holds exactly for Q = U H J H^T from a polar decomposition B = U R.The columns of H are orthonormalized eigenvectors of the symmetric factor R.
- Proof strategy: After transforming with U^T, the appendix reduces the problem to orthogonal T such that T^T R is symmetric and det(T) = det(U).This change of basis makes the structure of all solutions explicit.
- Eigenbasis analysis: In an eigenbasis H* of R, repeated eigenvalues permit diagonalization of the corresponding T submatrix.The eigenvalues are ordered λ_1 ≥ λ_2 ... ≥ λ_n ≥ 0.
- Eigenbasis analysis: Zero and distinct eigenvalue blocks force off-diagonal entries of T to vanish, leaving T diagonal.Orthogonality then restricts diagonal entries to 1 or −1.