Fast linear iterations for distributed averaging. (English) Zbl 1157.90347

Summary: We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several common heuristics that are based on the Laplacian of the associated graph.We show how problem structure can be exploited to speed up interior-point methods for solving the fastest distributed linear iteration problem, for networks with up to a thousand or so edges. We also describe a simple subgradient method that handles far larger problems, with up to 100 000 edges. We give several extensions and variations on the basic problem.


90B10 Deterministic network models in operations research
90C22 Semidefinite programming
90C35 Programming involving graphs or networks


Full Text: DOI


[1] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. optim., 5, 13-51, (1995) · Zbl 0833.90087
[2] A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization, Analysis, Algorithms, and Engineering Applications, MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA, 2001. · Zbl 0986.90032
[3] Benson, S.; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. optim., 10, 443-461, (2000) · Zbl 0997.90059
[4] D.P. Bertsekas, Nonlinear Programming, 2nd Edition, Athena Scientific, Belmont, MA, 1999.
[5] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge
[6] Blondel, V.; Tsitsiklis, J.N., NP-hardness of some linear control design problems, SIAM J. control optim., 35, 2118-2127, (1997) · Zbl 0892.93050
[7] Borwein, J.M.; Lewis, A.S., Convex analysis and nonlinear optimization, theory and examples, Canadian mathematical society books in mathematics, (2000), Springer New York
[8] S. Boyd, P. Diaconis, P. Parrilo, L. Xiao, Symmetry analysis of reversible Markov chains, Submitted to Internet Mathematics, December 2003, Also available online at: http://www.stanford.edu/ boyd/symmetry.html. · Zbl 1087.60057
[9] S. Boyd, P. Diaconis, L. Xiao, Fastest mixing Markov chain on a graph, SIAM Review, in press, Available at: http://www.stanford.edu/ boyd/fmmc.html. · Zbl 1063.60102
[10] Boyd, S.; El Ghaoui, L., Method of centers for minimizing generalized eigenvalues, Linear algebra appl., 188, 63-111, (1993) · Zbl 0781.65051
[11] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear matrix inequalities in system and control theory, (1994), SIAM Philadelphia
[12] Boyd, S.; Vandenberghe, L., Convex optimization, (2003), Cambridge University Press Cambridge, Available at http://www.stanford.edu/ boyd/cvxbook.html
[13] A. Fax, R.M. Murray, Graph Laplacians and vehicle formation stabilization, in: Proceedings of the 15th IFAC World Congress on Automatic Control, Barcelona, Spain, July 2002.
[14] A. Fax, R.M. Murray, Information flow and cooperative control of vehicle formations, in: Proceedings of the 15th IFAC World Congress on Automatic Control, Barcelona, Spain, July 2002. · Zbl 1365.90056
[15] M. Fazel, H. Hindi, S. Boyd, A rank minimization heuristic with application to minimum order system approximation, in: Proceedings American Control Conference, Vol. 6, Arlington, VA, June 2001, pp. 4734-4739.
[16] L. El Ghaoui, S.-I. Niculescu (Eds.), Advances on Linear Matrix Inequality Methods in Control, SIAM, Philadelphia, 1999.
[17] C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Vol. 207, Springer, Berlin, 2001. · Zbl 0968.05002
[18] Hassibi, A.; How, J.; Boyd, S., Low-authority controller design via convex optimization, AIAA J. guidance control dynam., 22, 6, 862-872, (1999)
[19] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM J. optim., 10, 3, 673-696, (2000) · Zbl 0960.65074
[20] Hiriart-Urruty, J.-B.; Lemaréchal, C., Convex analysis and minimization algorithms, (1993), Springer Berlin · Zbl 0795.49001
[21] A. Jadbabaie, J. Lin, A.S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Autom. Control 48(6) (2003) 988-1001. · Zbl 1364.93514
[22] Lewis, A.S.; Overton, M.L., Eigenvalue optimization, Acta num., 5, 149-190, (1996) · Zbl 0870.65047
[23] Lynch, N.A., Distributed algorithms, (1996), Morgan Kaufmann San Francisco, CA · Zbl 0877.68061
[24] Merris, R., Laplacian matrices of graphs: a survey, Linear algebra appl., 197, 143-176, (1994) · Zbl 0802.05053
[25] M. Mesbahi, On a dynamic extension of the theory of graphs, in: Proceedings of the American Control Conference, Anchorange, AL, May 2002.
[26] Meyer, C.D.; Plemmons, R.J., Convergence powers of a matrix with applications to iterative methods for singular linear systems, SIAM J. num. anal., 14, 4, 699-705, (1977) · Zbl 0366.65017
[27] L. Moreau, Stability of multi-agent system with time-dependent communication links, IEEE Trans. Automat. Control, in press. · Zbl 1365.93268
[28] D. Mustafa, K. Glover, Minimum Entropy H∞ Control, Lecture Notes in Control and Information Sciences, Vol. 146, Springer, Berlin, 1990. · Zbl 0707.93014
[29] Nemirovskii, A., Several NP-hard problems arising in robust stability analysis, Math. control signals systems, 6, 99-105, (1993) · Zbl 0792.93100
[30] A. Nemirovskii, Prox-method with rate of convergence O(1/t) for Lipschitz continuous variational inequalities and smooth convex-concave saddle point problems, Personal communication, 2003.
[31] Nesterov, Y.; Nemirovskii, A., Interior-point polynomial algorithms in convex programming, SIAM studies in applied mathematics, (1994), SIAM Philadelphia, PA · Zbl 0824.90112
[32] Oldenburger, R., Infinite powers of matrices and characteristic roots, Duke math. J., 6, 357-361, (1940) · JFM 66.1198.01
[33] R. Olfati-Saber, R.M. Murray, Consensus protocols for networks of dynamic agents, in: Proceedings of American Control Conference, Denver, CO, June 2003.
[34] Overton, M.L., Large-scale optimization of eigenvalues, SIAM J. optim., 2, 88-120, (1992) · Zbl 0757.65072
[35] Overton, M.L.; Womersley, R.S., On minimizing the spectral radius of a nonsymmetric matrix function—optimality conditions and duality theory, SIAM J. matrix anal. appl., 9, 473-498, (1988) · Zbl 0684.65062
[36] Overton, M.L.; Womersley, R.S., Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Math. programming, 62, 321-357, (1993) · Zbl 0806.90114
[37] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, NJ · Zbl 0431.65016
[38] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0229.90020
[39] Saad, Y., Numerical methods for large eigenvalue problems, (1992), Manchester University Press Manchester, UK · Zbl 0991.65039
[40] Shor, N.Z., Minimization methods for non-differentiable functions, Springer series in computational mathematics, (1985), Springer Berlin · Zbl 0561.90058
[41] Todd, M., Semidefinite optimization, Acta num., 10, 515-560, (2001) · Zbl 1105.65334
[42] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM rev., 38, 1, 49-95, (1996) · Zbl 0845.65023
[43] H. Wolkowicz, R. Saigal, L. Vandengerghe (Eds.), Handbook of Semidefinite Programming, Theory, Algorithms, and Applications, Kluwer Academic Publishers, Dordrecht, 2000.
[44] Ye, Y., Interior point algorithms: theory and analysis, wiey-interscience series in discrete mathematics and optimization, (1997), Wiley New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.