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.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C22 | Semidefinite programming |
| 90C35 | Programming involving graphs or networks |
Keywords:
Distributed consensus; Linear system; Spectral radius; Graph Laplacian; Semidefinite programmingSoftware:
COLReferences:
| [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.; 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.; D.P. Bertsekas, Nonlinear Programming, 2nd Edition, Athena Scientific, Belmont, MA, 1999. · Zbl 1015.90077 |
| [5] | Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: 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: Springer New York · Zbl 0953.90001 |
| [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.; 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.; 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: SIAM Philadelphia · Zbl 0816.93004 |
| [12] | Boyd, S.; Vandenberghe, L., Convex Optimization (2003), Cambridge University Press: 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.; 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.; 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.; 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.; 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.; 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: 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.; 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: 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.; 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.; 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.; 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.; 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: 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.; 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: Prentice-Hall Englewood Cliffs, NJ · Zbl 0431.65016 |
| [38] | Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020 |
| [39] | Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester University Press: 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: 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.; H. Wolkowicz, R. Saigal, L. Vandengerghe (Eds.), Handbook of Semidefinite Programming, Theory, Algorithms, and Applications, Kluwer Academic Publishers, Dordrecht, 2000. · Zbl 0962.90001 |
| [44] | Ye, Y., Interior Point Algorithms: Theory and Analysis, Wiey-Interscience Series in Discrete Mathematics and Optimization (1997), Wiley: Wiley New York · Zbl 0943.90070 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
