PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for leader selection in stochastically forced consensus networks

Fu Lin, Makan Fardad, Mihailo R. Jovanović

arXiv:1302.0450v2math.OCcs.ROeess.SY

TL;DR

The paper asks how to select a fixed number of leaders to reduce mean-square consensus deviation in stochastically forced networks. It develops convex relaxations, greedy selection procedures, and a customized large-scale algorithm for noise-corrupted and noise-free formulations. The resulting methods provide lower and upper performance bounds and semidefinite-program relaxations for leader selection.

  • Problem

    The paper studies how to identify a fixed number of leaders that most effectively reduce steady-state consensus deviation in stochastically forced networks.

  • Method

    The paper relaxes Boolean constraints for noise-corrupted networks, drops the rank constraint for noise-free networks, and combines SDP-based methods with greedy and swap procedures.

  • Results

    The algorithms compute lower and upper bounds for noise-corrupted leader selection and provide an SDP relaxation with ADMM for large-scale noise-free problems.

  • Takeaways & Limitations

    The computational methods make performance bounds and leader identification feasible for large stochastically forced networks.

Abstract

from arXiv · show

We are interested in assigning a pre-specified number of nodes as leaders in order to minimize the mean-square deviation from consensus in stochastically forced networks. This problem arises in several applications including control of vehicular formations and localization in sensor networks. For networks with leaders subject to noise, we show that the Boolean constraints (a node is either a leader or it is not) are the only source of nonconvexity. By relaxing these constraints to their convex hull we obtain a lower bound on the global optimal value. We also use a simple but efficient greedy algorithm to identify leaders and to compute an upper bound. For networks with leaders that perfectly follow their desired trajectories, we identify an additional source of nonconvexity in the form of a rank constraint. Removal of the rank constraint and relaxation of the Boolean constraints yields a semidefinite program for which we develop a customized algorithm well-suited for large networks. Several examples ranging from regular lattices to random graphs are provided to illustrate the effectiveness of the developed algorithms.

I. INTRODUCTION

The paper studies leader selection for minimizing consensus deviation in stochastically forced networks, with applications including vehicular formations and sensor localization. It develops convex relaxations and greedy algorithms to bound optimal performance in noise-corrupted networks, then extends the framework to noise-free leaders with an additional rank constraint.

  • Problem formulation: The goal is to assign a pre-specified number of leaders that minimize mean-square deviation from consensus.The setting includes undirected networks with followers using relative information and leaders having access to their own states.
  • Noise-corrupted networks: For noise-corrupted networks, Boolean leader-selection constraints are the only source of nonconvexity.Their combinatorial structure makes finding the global minimum challenging.
  • Noise-corrupted networks: Relaxing Boolean constraints to their convex hull yields a lower bound, while a greedy algorithm identifies leaders and computes an upper bound.The relaxation can be formulated as a semidefinite program for small networks.
  • Computational methods: Customized algorithms exploit low-rank Laplacian modifications and leader-swap procedures to reduce computational complexity for large networks.The greedy approach is improved by checking possible swaps between leaders and followers.
  • Noise-free networks: For noise-free leaders, the problem has an additional nonconvex rank constraint, so the paper drops it, relaxes Boolean constraints, and applies ADMM to the resulting SDP.A greedy procedure followed by swaps computes an upper bound and selects leaders.
  • Problem formulations: The two formulations require separate convex relaxations and customized algorithms and are independently relevant from application, formulation, and algorithmic perspectives.The resulting methods are intended to establish achievable performance bounds in large stochastically forced networks.

II. PROBLEM FORMULATION

The paper formulates leader selection in consensus networks as choosing a prescribed number of leaders to reduce steady-state variance under stochastic disturbances. It distinguishes noise-corrupted and noise-free leaders and identifies the respective optimization structure and nonconvexities.

  • A. Leader selection problem in consensus networks: The network consists of nodes updating scalar states through neighbor communication, with leaders additionally accessing their own states to form control actions.The communication graph is connected and undirected, and the control objective is to strategically deploy leaders to reduce variance amplification.
  • A. Leader selection problem in consensus networks: Each node’s Boolean variable indicates whether it is a leader, while the fixed leader count Nl constrains the selection.The vector x is the optimization variable, and Nl, L, and Dκ are problem data.
  • A. Leader selection problem in consensus networks: For noise-corrupted leaders, total steady-state variance quantifies performance, and selecting Nl leaders minimizes this variance subject to Boolean constraints.The state covariance is obtained from a Lyapunov equation, and the objective is the total steady-state variance.
  • A. Leader selection problem in consensus networks: The noise-corrupted problem has a convex objective for positive definite L + DκD_x, but its Boolean constraints make the overall search combinatorial and intractable.The Boolean constraints are the only source of nonconvexity in this formulation.
  • A. Leader selection problem in consensus networks: When leaders perfectly follow desired trajectories, the dynamics reduce to the followers, whose variance is minimized through a separate leader-selection formulation.The follower Laplacian Lf is formed by eliminating rows and columns associated with leaders.
  • A. Leader selection problem in consensus networks: The noise-free problem retains nonconvex Boolean constraints and additionally has a nonconvex objective function of the selection vector.Thus, it cannot generally be obtained from the noise-corrupted problem simply by setting leader disturbance variance to zero.
  • A. Leader selection problem in consensus networks: The two formulations become equivalent when noise-corrupted leaders use arbitrarily large feedback gains on their own states, because their disturbance variance tends to zero.The variance of noise-corrupted leaders decreases to zero as feedback gains increase to infinity.

B. Connections to the sensor selection problem

The paper connects relative-measurement sensor localization to leader selection by showing that absolute-position sensor placement problems are equivalent to leader-selection formulations. This connection covers both noise-corrupted and noise-free settings.

  • Measurement model: The localization formulation uses relative measurements between distinct node pairs and absolute measurements at selected sensors.The relative-measurement matrix is built from vectors with 1 and −1 at the measured nodes, while absolute measurements use selected unit-vector columns.
  • Measurement model: Relative measurements estimate sensor positions only up to an additive constant.The invariance follows because adding the same scalar to every position leaves all relative measurements unchanged.
  • Noise-corrupted leaders: Selecting Nl sensors for absolute position measurements to minimize estimation-error variance is equivalent to noise-corrupted leader selection.Absolute measurements are modeled through sensors equipped with GPS devices and stochastic disturbances.
  • Noise-free leaders: When sensor positions are known a priori, assigning Nl sensors to minimize estimation-error variance corresponds to the noise-free leader selection problem.The paper identifies this formulation for localization settings in which positions are known beforehand.

III. LOWER AND UPPER BOUNDS ON GLOBAL PERFORMANCE: NOISE-CORRUPTED LEADERS

For noise-corrupted leaders, the objective is convex in the leader-selection variables, so relaxing Boolean constraints gives a lower bound and greedy selection gives an upper bound. Low-rank updates make both procedures computationally practical for large networks.

  • Convex relaxation: The noise-corrupted leader-selection objective J is convex, enabling efficient computation of lower and upper bounds on the global optimum.The convexity follows from composing trace of an inverse positive-definite matrix with an affine matrix function.
  • Computational efficiency: The approach includes an SDP formulation for the relaxation and a customized interior-point method for large networks.Standard SDP solvers are noted for small networks, while the customized method targets larger instances.
  • Convex relaxation: Relaxing xi ∈ {0, 1} to 0 ≤ xi ≤ 1 with 1^T x = Nl yields a convex relaxation whose optimum is a lower bound.The relaxed solution is globally optimal for the original problem if it remains Boolean-valued; otherwise it may not define a leader set.
  • Greedy upper bound: A greedy algorithm obtains an upper bound by selecting one leader at a time according to the largest performance improvement, followed by possible leader-follower swaps.The method exploits low-rank modifications of Laplacian matrices and the matrix inversion lemma for efficiency.
  • Computational efficiency: The customized implementation reduces the greedy computation from O(n^4Nl) operations without structure exploitation to O(n^2Nl + n^3).The reduced cost uses rank-1 updates, objective evaluations, and one full matrix inverse.

2) Swap algorithm:

The swap algorithm locally improves a greedy leader set by testing leader-follower exchanges, using rank-2 updates to evaluate candidates efficiently. In the random-network example, the resulting bounds converge as more leaders are selected, and greedy selection outperforms degree heuristics.

  • Swap algorithm: The swap algorithm tests exchanges between each leader and follower, retaining a swap whenever it decreases the objective and stopping when no improving exchange remains.The procedure can limit the maximum number of swaps or exploit network structure to reduce them.
  • Swap algorithm: Rank-2 Laplacian modifications and the matrix inversion lemma reduce the cost of evaluating leader-follower swaps.The inverse update requires O(n^2) operations, while individual objective evaluations require O(n).
  • Symmetry example: A nine-node lattice example uses symmetry to restrict candidate swaps to one representative node from each equivalent node set.With node 5 initially selected, swaps need only be checked against one node in each of S1 and S2.
  • Random-network results: As Nl increases, the gap between convex-relaxation lower bounds and greedy upper bounds decreases in the random-network example.For Nl = 1, . . . , 40, swap updates range from 1 to 26, with an average of 8 swaps.
  • Random-network results: The greedy algorithm significantly outperforms degree-based selection in the random-network example.Degree heuristics cluster leaders near the network center, whereas greedy selection distributes them around the boundary and selects leaders far apart.

2) A 2D lattice:

For a 2D lattice, convex relaxations and greedy methods provide bounds and scalable computation for leader selection, while the noise-free formulation adds rank-induced nonconvexity. Greedy selections show symmetry and increasingly uniform spacing as more leaders are chosen.

  • 2D lattice: The noise-corrupted lattice uses convex relaxation for a lower bound and a greedy algorithm for an upper bound.The resulting bounds quantify performance for a 2D regular lattice with 81 nodes.
  • 2D lattice: For Nl = 1, . . . , 40, the performance gap decreases with Nl, while swap updates range from 1 to 19 and average 10.
  • 2D lattice: The single-leader optimum is the center node (5, 5), while additional leaders move away from the center.For Nl = 2, the selected nodes are {(3, 3), (7, 7)}; for Nl = 3, they are {(2, 6), (6, 2), (8, 8)}.
  • 2D lattice: Lattice leader selections are symmetric about the center and become almost uniformly spaced when Nl is large.The text contrasts this pattern with boundary-node selections in a random network.
  • Noise-free selection: Dropping the rank constraint and relaxing Boolean variables to [0, 1] yields a convex semidefinite relaxation solved with a customized ADMM-based approach.The separable constraint structure is exploited to develop an efficient algorithm for large problems.

1) (Y, y)-minimization step:

The (Y, y)-minimization step solves a smooth convex problem over the positive semidefinite cone and updates y without additional constraints. Gradient projection maintains feasibility and has O(n^3) iteration cost.

  • (Y, y)-minimization step: The Y gradient combines the inverse-based objective gradient with a quadratic penalty involving Y − U^k.
  • (Y, y)-minimization step: The (Y, y)-minimization step minimizes a smooth convex function over Y ⪰ 0 while updating y by standard unconstrained descent.
  • (Y, y)-minimization step: The y gradient uses the diagonal of the squared inverse matrix plus a quadratic penalty involving y − u^k.
  • (Y, y)-minimization step: Gradient projection terminates when Y and its gradient satisfy positive-semidefinite KKT conditions and the y-gradient norm is below ϵ.
  • (Y, y)-minimization step: Each gradient-projection iteration takes O(n^3) operations because it requires eigenvalue decomposition and matrix inversion.
  • (Y, y)-minimization step: The (Z, z)-minimization step decomposes into independent projections onto convex sets, including simplex constraints for z.For Nf ≥ 2, an ADMM-based alternating projection method handles the simplex projection.

D. Greedy algorithm to obtain an upper bound

The greedy upper-bound method selects leaders one at a time by minimizing the objective, then improves the result through swaps. Low-rank updates reduce the computational cost of repeated evaluations.

  • D. Greedy algorithm to obtain an upper bound: The one-at-a-time greedy algorithm selects each next leader by minimizing the objective until all Nl leaders are chosen.
  • D. Greedy algorithm to obtain an upper bound: Ignoring low-rank structure costs O(n^4Nl), while exploiting rank-2 updates reduces the greedy complexity to O(n^3Nl).
  • D. Greedy algorithm to obtain an upper bound: After greedy selection, a swap algorithm exchanges leaders and followers to further improve performance.
  • D. Greedy algorithm to obtain an upper bound: Each leader-follower swap creates a rank-2 modification, allowing objective evaluation with O(n^2) operations.

E. An example

In a 200-node C-shaped sensor-localization benchmark, the developed methods produce decreasing lower–upper bound gaps as the number of leaders increases. The selected leaders tend to have large degrees and similar patterns across noise models.

  • E. An example: The example contains 200 randomly distributed nodes in a C-shaped region, with communication for node pairs within 0.1 units.The network is used as a benchmark for sensor localization algorithms.
  • E. An example: The gap between lower and upper bounds decreases as Nl increases in the noise-free leader selection problem.
  • E. An example: For Nl = 1, . . . , 10, swap updates range from 1 to 16 and average 8.
  • E. An example: The greedy algorithm selects leaders with large degrees that are geographically far from one another.
  • E. An example: Noise-free and noise-corrupted formulations produce almost identical leader selections in the C-shaped network.

V. CONCLUDING REMARKS

The paper develops efficient algorithms for leader selection in large stochastically forced consensus networks, using convex relaxations for lower bounds and greedy methods for upper bounds. It also identifies open questions concerning convex-relaxation solutions and low-rank bounds.

  • The paper develops efficient algorithms for selecting leaders in large stochastically forced consensus networks.
  • Lower bounds come from convex relaxations, while simple greedy algorithms provide upper bounds on the global optimal value.
  • The algorithms exploit problem structure, including separable constraint sets, to improve computational efficiency for large-scale networks.
  • Examples spanning regular lattices and random networks illustrate the effectiveness of the developed algorithms.
  • An open question is whether leaders can be selected from convex-relaxation solutions, including cases where the relaxation has dominant eigenvalues or yields a rank-1 solution.

APPENDIX

The appendix establishes equivalences between leader-selection and sensor-selection formulations. It relates leader placement to minimizing estimation error variance under absolute position measurements and reference sensors.

  • Partitioning the state into leader and follower components produces a reduced formulation involving the follower-state dynamics.
  • The leader-associated feedback gains determine the accuracy of absolute measurements, with larger κ_i corresponding to more accurate measurements.
  • The noise-corrupted leader-selection problem is equivalent to choosing sensors with absolute position measurements to minimize estimation-error variance.
  • Assigning sensors known reference positions is equivalent to minimizing the variance of the sensor-network estimation error.
  • The noise-free leader-selection problem is formulated by assuming that selected sensor positions are known a priori as reference positions.

C. Customized interior point method for (CR1)

The customized interior-point method solves the convex relaxation (CR1) by a sequence of log-barrier problems and Newton steps. An ADMM-based procedure handles the hyperplane and box constraints using efficient projections.

  • The method augments the (CR1) objective with log-barrier functions for the inequality constraints on x_i.
  • As τ increases to infinity, the approximate problem converges to the convex relaxation (CR1), solved through a sequence of problems.
  • Newton’s method solves each fixed-τ problem, using the previous solution to initialize the next minimization.
  • Each Newton step requires (11/3)n^3 operations after forming the inverse and solving the associated linear equations.
  • ADMM separates the hyperplane constraint 1^Tz = N_f from the unit-box constraint, and both resulting updates take O(n) operations.
Loading 1302.0450v2…