Choon Yik Tang

Jie Lu, Choon Yik Tang

This paper presents a set of continuous-time distributed algorithms that solve unconstrained, separable, convex optimization problems over undirected networks with fixed topologies. The algorithms are developed using a Lyapunov function candidate that exploits convexity, and are called Zero-Gradient-Sum (ZGS) algorithms as they yield nonlinear networked dynamical systems that evolve invariantly on a zero-gradient-sum manifold and converge asymptotically to the unknown optimizer. We also describe a systematic way to construct ZGS algorithms, show that a subset of them actually converge exponentially, and obtain lower and upper bounds on their convergence rates in terms of the network topologies, problem characteristics, and algorithm parameters, including the algebraic connectivity, Laplacian spectral radius, and function curvatures. The findings of this paper may be regarded as a natural generalization of several well-known algorithms and results for distributed consensus, to distributed convex optimization.

Choon Yik Tang, Jie Lu

This paper addresses the problem of averaging numbers across a wireless network from an important, but largely neglected, viewpoint: bandwidth/energy efficiency. We show that existing distributed averaging schemes have several drawbacks and are inefficient, producing networked dynamical systems that evolve with wasteful communications. Motivated by this, we develop Controlled Hopwise Averaging (CHA), a distributed asynchronous algorithm that attempts to "make the most" out of each iteration by fully exploiting the broadcast nature of wireless medium and enabling control of when to initiate an iteration. We show that CHA admits a common quadratic Lyapunov function for analysis, derive bounds on its exponential convergence rate, and show that they outperform the convergence rate of Pairwise Averaging for some common graphs. We also introduce a new way to apply Lyapunov stability theory, using the Lyapunov function to perform greedy, decentralized, feedback iteration control. Finally, through extensive simulation on random geometric graphs, we show that CHA is substantially more efficient than several existing schemes, requiring far fewer transmissions to complete an averaging task.

Jie Lu, Choon Yik Tang

This paper considers the problem of solving a symmetric positive definite system of linear equations over a network of agents with arbitrary asynchronous interactions and membership dynamics. The latter implies that each agent is allowed to join and leave the network at any time, for infinitely many times, and lose all its memory upon leaving. We develop Subset Equalizing (SE), a distributed asynchronous algorithm for solving such a problem. To design and analyze SE, we introduce a novel time-varying Lyapunov-like function, defined on a state space with changing dimension, and a generalized concept of network connectivity, capable of handling such interactions and membership dynamics. Based on them, we establish the boundedness, asymptotic convergence, and exponential convergence of SE, along with a bound on its convergence rate. Finally, through extensive simulation, we show that SE is effective in a volatile agent network and that a special case of SE, termed Groupwise Equalizing, is significantly more bandwidth/energy efficient than two existing algorithms in multi-hop wireless networks.

Mu Yang, Choon Yik Tang

In this paper, we develop a two-stage distributed algorithm that enables nodes in a graph to cooperatively estimate the spectrum of a matrix $W$ associated with the graph, which includes the adjacency and Laplacian matrices as special cases. In the first stage, the algorithm uses a discrete-time linear iteration and the Cayley-Hamilton theorem to convert the problem into one of solving a set of linear equations, where each equation is known to a node. In the second stage, if the nodes happen to know that $W$ is cyclic, the algorithm uses a Lyapunov approach to asymptotically solve the equations with an exponential rate of convergence. If they do not know whether $W$ is cyclic, the algorithm uses a random perturbation approach and a structural controllability result to approximately solve the equations with an error that can be made small. Finally, we provide simulation results that illustrate the algorithm.

Jie Lu, Choon Yik Tang, Paul R. Regier et al.

In many applications, nodes in a network desire not only a consensus, but an optimal one. To date, a family of subgradient algorithms have been proposed to solve this problem under general convexity assumptions. This paper shows that, for the scalar case and by assuming a bit more, novel non-gradient-based algorithms with appealing features can be constructed. Specifically, we develop Pairwise Equalizing (PE) and Pairwise Bisectioning (PB), two gossip algorithms that solve unconstrained, separable, convex consensus optimization problems over undirected networks with time-varying topologies, where each local function is strictly convex, continuously differentiable, and has a minimizer. We show that PE and PB are easy to implement, bypass limitations of the subgradient algorithms, and produce switched, nonlinear, networked dynamical systems that admit a common Lyapunov function and asymptotically converge. Moreover, PE generalizes the well-known Pairwise Averaging and Randomized Gossip Algorithm, while PB relaxes a requirement of PE, allowing nodes to never share their local functions.