1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 1, 2018
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 1, 2018

Distributed Optimization for Control

Abstract

Advances in wired and wireless technology have necessitated the development of theory, models, and tools to cope with the new challenges posed by large-scale control and optimization problems over networks. The classical optimization methodology works under the premise that all problem data are available to a central entity (a computing agent or node). However, this premise does not apply to large networked systems, where each agent (node) in the network typically has access only to its private local information and has only a local view of the network structure. This review surveys the development of such distributed computational models for time-varying networks. To emphasize the role of the network structure in these approaches, we focus on a simple direct primal (sub)gradient method, but we also provide an overview of other distributed methods for optimization in networks. Applications of the distributed optimization framework to the control of power systems, least squares solutions to linear equations, and model predictive control are also presented.

Keyword(s): agent networks, distributed optimization, multi-agent systems
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-060117-105131
2018-05-28
2024-04-19
Loading full text...

Full text loading...

/deliver/fulltext/control/1/1/annurev-control-060117-105131.html?itemId=/content/journals/10.1146/annurev-control-060117-105131&mimeType=html&fmt=ahah

Literature Cited

  1. 1.  Bash BA, Desnoyers PJ 2007. Exact distributed Voronoi cell computation in sensor networks. 2007 6th International Symposium on Information Processing in Sensor Networks236–43 New York: IEEE
     [Google Scholar]
  2. 2.  DeGroot M 1974. Reaching a consensus. J. Am. Stat. Assoc. 69:118–21
     [Google Scholar]
  3. 3.  Borkar V, Varaiya P 1982. Asymptotic agreement in distributed estimation. IEEE Trans. Autom. Control 27:650–55
     [Google Scholar]
  4. 4.  Tsitsiklis J 1984. Problems in decentralized decision making and computation PhD Thesis, Dep. Electr. Eng. Comput. Sci., Mass. Inst. Technol Cambridge, MA:
  5. 5.  Jadbabaie A, Lin J, Morse A 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control 48:988–1001
     [Google Scholar]
  6. 6.  Kempe D, Dobra A, Gehrke J 2003. Gossip-based computation of aggregate information. 2003 44th Annual IEEE Symposium on Foundations of Computer Science482–91 New York: IEEE
     [Google Scholar]
  7. 7.  Olfati-Saber R, Murray RM 2004. Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. Autom. Control 49:1520–33
     [Google Scholar]
  8. 8.  Moreau L 2005. Stability of multiagent systems with time-dependent communication links. IEEE Trans. Autom. Control 50:169–82
     [Google Scholar]
  9. 9.  Vicsek T, Czirok A, Ben-Jacob E, Cohen I, Schochet O 1995. Novel type of phase transitions in a system of self-driven particles. Phys. Rev. Lett. 75:1226–29
     [Google Scholar]
  10. 10.  Bullo F, Cortés J, Martínez S 2009. Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms Princeton, NJ: Princeton Univ. Press
  11. 11.  Mesbahi M, Egerstedt M 2010. Graph Theoretic Methods for Multiagent Networks Princeton, NJ: Princeton Univ. Press
  12. 12.  Martinoli A, Mondada F, Mermoud G, Correll N, Egerstedt M et al., eds. 2013. Distributed Autonomous Robotic Systems: The 10th International Symposium Berlin: Springer
  13. 13.  Nedić A, Olshevsky A, Ozdaglar A, Tsitsiklis J 2009. On distributed averaging algorithms and quantization effects. IEEE Trans. Autom. Control 54:2506–17
     [Google Scholar]
  14. 14.  Facchinei F, Pang JS 2003. Finite-Dimensional Variational Inequalities and Complementarity Problems New York: Springer
  15. 15.  Nedić A 2015. Convergence Rate of Distributed Averaging Dynamics and Optimization in Networks Found. Trends Syst. Control Vol. 2 No. 1 Hanover, MA: Now
  16. 16.  Lopes CG, Sayed AH 2007. Distributed processing over adaptive networks. 2007 9th International Symposium on Signal Processing and Its Applications New York: IEEE https://doi.org/10.1109/ISSPA.2007.4555636
    [Crossref] [Google Scholar]
  17. 17.  Nedić A, Ozdaglar A 2009. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom. Control 54:48–61
     [Google Scholar]
  18. 18.  Nedić A, Ozdaglar A 2010. Cooperative distributed multi-agent optimization. Convex Optimization in Signal Processing and Communications Y Eldar, D Palomar 340–86 Cambridge, UK: Cambridge Univ. Press
     [Google Scholar]
  19. 19.  Nedić A, Ozdaglar A 2007. On the rate of convergence of distributed subgradient methods for multi-agent optimization. 2007 46th IEEE Conference on Decision and Control4711–16 New York: IEEE
     [Google Scholar]
  20. 20.  Nedić A, Olshevsky A, Ozdaglar A, Tsitsiklis J 2008. Distributed subgradient methods and quantization effects. 2008 47th IEEE Conference on Decision and Control4177–84 New York: IEEE
     [Google Scholar]
  21. 21.  Lobel I, Ozdaglar A 2011. Distributed subgradient methods for convex optimization over random networks. IEEE Trans. Autom. Control 56:1291–306
     [Google Scholar]
  22. 22.  Lopes C, Sayed A 2008. Diffusion least-mean squares over adaptive networks: formulation and performance analysis. IEEE Trans. Signal Process. 56:3122–36
     [Google Scholar]
  23. 23.  Tu SY, Sayed A 2012. Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Trans. Signal Process. 60:6217–34
     [Google Scholar]
  24. 24.  Nedić A, Ozdaglar A, Parrilo P 2010. Constrained consensus and optimization in multi-agent networks. IEEE Trans. Autom. Control 55:922–38
     [Google Scholar]
  25. 25.  Lee S 2013. Optimization over networks: efficient algorithms and analysis PhD Thesis, Dep. Electr. Comput. Eng., Univ. Ill Urbana-Champaign:
  26. 26.  Lee S, Nedić A 2012. Distributed random projection algorithm for convex optimization. IEEE J. Sel. Top. Signal Process. 48:988–1001
     [Google Scholar]
  27. 27.  Lee S, Nedić A 2016. Asynchronous gossip-based random projection algorithms over networks. IEEE Trans. Autom. Control 61:953–68
     [Google Scholar]
  28. 28.  Srivastava K, Nedić A, Stipanović D 2010. Distributed constrained optimization over noisy networks. 2010 49th IEEE Conference on Decision and Control (CDC)1945–50 New York: IEEE
     [Google Scholar]
  29. 29.  Srivastava K, Nedić A 2011. Distributed asynchronous constrained stochastic optimization. IEEE J. Sel. Top. Signal Process. 5:772–90
     [Google Scholar]
  30. 30.  Srivastava K 2011. Distributed optimization with applications to sensor networks and machine learning PhD Thesis, Dep. Ind. Enterp. Syst. Eng., Univ. Ill Urbana-Champaign:
  31. 31.  Cattivelli F, Sayed A 2010. Diffusion LMS strategies for distributed estimation. IEEE Trans. Signal Process. 58:1035–48
     [Google Scholar]
  32. 32.  Tu SY, Sayed A 2012. On the influence of informed agents on learning and adaptation over networks. IEEE Trans. Signal Process. 61:1339–56
     [Google Scholar]
  33. 33.  Chen J, Sayed A 2012. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Trans. Signal Process. 60:4289–305
     [Google Scholar]
  34. 34.  Ram S, Nedić A, Veeravalli V 2012. A new class of distributed optimization algorithms: application to regression of distributed data. Optim. Methods Softw. 27:71–88
     [Google Scholar]
  35. 35.  Shahrampour S, Jadbabaie A 2013. Exponentially fast parameter estimation in networks using distributed dual averaging. In 2013 IEEE 52nd Annual Conference on Decision and Control (CDC)6196–201 New York: IEEE
     [Google Scholar]
  36. 36.  Shahrampour S, Rakhlin A, Jadbabaie A 2015. Distributed detection: finite-time analysis and impact of network topology. IEEE Trans. Autom. Control 61:3256–68
     [Google Scholar]
  37. 37.  Lalitha A, Javidi T, Sarwate A 2014. Social learning and distributed hypothesis testing. 2014 IEEE International Symposium on Information Theory (ISIT)551–55 New York: IEEE
     [Google Scholar]
  38. 38.  Nedić A, Olshevsky A, Uribe C 2015. Nonasymptotic convergence rates for cooperative learning over time-varying directed graphs. 2015 American Control Conference (ACC)5884–89 New York: IEEE
     [Google Scholar]
  39. 39.  Nedić A, Olshevsky A, Uribe C 2016. Network independent rates in distributed learning. 2016 American Control Conference (ACC)1072–77 New York: IEEE
     [Google Scholar]
  40. 40.  Srivastava K, Nedić A, Stipanovic D 2013. Distributed Bregman-distance algorithms for min-max optimization. In Agent-Based Optimization I Czarnowski, P Jedrzejowicz, J Kacprzyk 143–74 Berlin: Springer
     [Google Scholar]
  41. 41.  Koshal J, Nedić A, Shanbhag U 2016. Distributed algorithms for aggregative games on graphs. Oper. Res. 64:680–704
     [Google Scholar]
  42. 42.  Duchi J, Agarwal A, Wainwright M 2012. Dual averaging for distributed optimization: convergence analysis and network scaling. IEEE Trans. Autom. Control 57:592–606
     [Google Scholar]
  43. 43.  Shi W, Ling Q, Wu G, Yin W 2015. EXTRA: an exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25:944–66
     [Google Scholar]
  44. 44.  Lu J, Tang C 2012. Zero-gradient-sum algorithms for distributed convex optimization: the continuous-time case. IEEE Trans. Autom. Control 57:2348–54
     [Google Scholar]
  45. 45.  Gharesifard B, Cortés J 2012. Distributed continuous-time convex optimization on weight-balanced digraphs. Eur. J. Control 18:539–57
     [Google Scholar]
  46. 46.  Li N, Marden JR 2013. Designing games for distributed optimization. IEEE J. Sel. Top. Signal Process. 7:230–42
     [Google Scholar]
  47. 47.  Nedić A, Lee S, Raginsky M 2015. Decentralized online optimization with global objectives and local communication. 2015 American Control Conference (ACC)4497–503 New York: IEEE
     [Google Scholar]
  48. 48.  Lee S, Nedić A, Raginsky M 2018. Coordinate dual averaging for decentralized online optimization with non-separable global objectives. IEEE Trans. Control Netw. Syst. 5:34–44
     [Google Scholar]
  49. 49.  Jakovetić D, Xavier J, Moura J 2011. Cooperative convex optimization in networked systems: augmented Lagrangian algorithms with directed gossip communication. IEEE Trans. Signal Process. 59:3889–902
     [Google Scholar]
  50. 50.  Jakovetić D, Xavier J, Moura J 2014. Fast distributed gradient methods. IEEE Trans. Autom. Control 59:1131–46
     [Google Scholar]
  51. 51.  Zhu M, Martínez S 2012. On distributed convex optimization under inequality and equality constraints. IEEE Trans. Autom. Control 57:151–64
     [Google Scholar]
  52. 52.  Zhu M, Martínez S 2013. An approximate dual subgradient algorithm for distributed non-convex constrained optimization. IEEE Trans. Autom. Control 58:1534–39
     [Google Scholar]
  53. 53.  Chang TH, Nedić A, Scaglione A 2014. Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans. Autom. Control 59:1524–38
     [Google Scholar]
  54. 54.  Wang J, Elia N 2011. A control perspective for centralized and distributed convex optimization. 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)3800–5 New York: IEEE
     [Google Scholar]
  55. 55.  Wan P, Lemmon M 2009. Event-triggered distributed optimization in sensor networks. 2009 International Conference on Information Processing of Sensor Networks49–60 New York: IEEE
     [Google Scholar]
  56. 56.  Bürger M, Notarstefano G, Bullo F, Allgöwer F 2012. A distributed simplex algorithm for degenerate linear programs and multi-agent assignments. Automatica 48:2298–304
     [Google Scholar]
  57. 57.  Zanella F, Varagnolo D, Cenedese A, Pillonetto G, Schenato L 2011. Newton-Raphson consensus for distributed convex optimization. 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)5917–22 New York: IEEE
     [Google Scholar]
  58. 58.  Lobel I, Ozdaglar A, Feijer D 2011. Distributed multi-agent optimization with state-dependent communication. Math. Prog. 129:255–84
     [Google Scholar]
  59. 59.  Dominguez-Garcia A, Hadjicostis C 2011. Distributed strategies for average consensus in directed graphs. 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)2124–29 New York: IEEE
     [Google Scholar]
  60. 60.  Benezit F, Blondel V, Thiran P, Tsitsiklis J, Vetterli M 2010. Weighted gossip: distributed averaging using non-doubly stochastic matrices. In 2010 IEEE International Symposium on Information Theory (ISIT)1753–57 New York: IEEE
     [Google Scholar]
  61. 61.  Tsianos K, Lawlor S, Rabbat M 2012. Consensus-based distributed optimization: practical issues and applications in large-scale machine learning. 2012 50th Allerton Conference on Communication, Control, and Computing1543–50 New York: IEEE
     [Google Scholar]
  62. 62.  Tsianos K, Lawlor S, Rabbat M 2012. Push-sum distributed dual averaging for convex optimization. 2012 IEEE 51st Annual Conference on Decision and Control (CDC)5453–58 New York: IEEE
     [Google Scholar]
  63. 63.  Tsianos K, Rabbat M 2011. Distributed consensus and optimization under communication delays. 2011 49th Annual Allerton Conference on Communication, Control, and Computing974–82 New York: IEEE
     [Google Scholar]
  64. 64.  Tsianos K 2013. The role of the network in distributed optimization algorithms: convergence rates, scalability, communication/computation tradeoffs and communication delays PhD Thesis, Dep. Electr. Comput. Eng., McGill Univ Montreal, Can.:
  65. 65.  Nedić A, Olshevsky A 2015. Distributed optimization over time-varying directed graphs. IEEE Trans. Autom. Control 60:601–5
     [Google Scholar]
  66. 66.  Nedić A, Olshevsky A 2016. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans. Autom. Control 61:3936–47
     [Google Scholar]
  67. 67.  Sun Y, Scutari G, Palomar D 2016. Distributed nonconvex multiagent optimization over time-varying networks. 2016 50th Asilomar Conference on Signals, Systems and Computers788–94 New York: IEEE
     [Google Scholar]
  68. 68.  Boyd S, Parikh N, Chu E, Peleato B, Eckstein J 2010. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers Found. Trends Mach. Learn . Vol. 3No. 1 Hanover, MA: Now
  69. 69.  Wei E, Ozdaglar A 2012. Distributed alternating direction method of multipliers. 2012 IEEE 51st Conference on Decision and Control (CDC)5445–50 New York: IEEE
     [Google Scholar]
  70. 70.  Wei E, Ozdaglar A 2013. On the O(1/k) convergence of asynchronous distributed alternating direction method of multipliers. In 2013 IEEE Global Conference on Signal and Information Processing (GlobalSIP). 551–54 New York: IEEE
  71. 71.  Ling Q, Ribeiro A 2014. Decentralized dynamic optimization through the alternating direction method of multiplier. IEEE Trans. Signal Process. 62:1185–97
     [Google Scholar]
  72. 72.  Shi W, Ling Q, Yuan K, Wu G, Yin W 2014. On the linear convergence of the ADMM in decentralized consensus optimization. IEEE Trans. Signal Process. 62:1750–61
     [Google Scholar]
  73. 73.  Aybat NS, Wang Z, Lin T, Ma S 2017. Distributed linearized alternating direction method of multipliers for composite convex consensus optimization. IEEE Trans. Autom. Control 63:5–20
     [Google Scholar]
  74. 74.  Shi W, Ling Q, Wu G, Yin W 2015. A proximal gradient algorithm for decentralized composite optimization. IEEE Trans. Signal Process. 63:6013–23
     [Google Scholar]
  75. 75.  Xi C, Khan U 2015. On the linear convergence of distributed optimization over directed graphs. arXiv1510.02149
  76. 76.  Zeng J, Yin W 2015. ExtraPush for convex smooth decentralized optimization over directed networks. arXiv1511.02942
  77. 77.  Xu J, Zhu S, Soh Y, Xie L 2015. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. 2015 IEEE 54th Conference on Decision and Control (CDC)2055–60 New York: IEEE
     [Google Scholar]
  78. 78.  Xu J 2016. Augmented distributed optimization for networked systems PhD Thesis, Sch. Electr. Electron. Eng., Nanyang Technol. Univ Singapore:
  79. 79.  Sayed A 2013. Diffusion adaptation over networks. Array and Statistical Signal Processing AM Zoubir, M Viberg, R Chellappa, S Theodoridis 323–453 Acad. Press Libr. Signal Process . Vol. 3 Oxford, UK: Academic
     [Google Scholar]
  80. 80.  Sayed AH 2014. Adaptation, learning, and optimization over networks. Found. Trends Mach. Learn. 7:311–801
     [Google Scholar]
  81. 81.  Zhu M, Martínez S 2010. Discrete-time dynamic average consensus. Automatica 46:322–29
     [Google Scholar]
  82. 82.  Di Lorenzo P, Scutari G 2015. Distributed nonconvex optimization over networks. 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015)229–32 New York: IEEE
     [Google Scholar]
  83. 83.  Di Lorenzo P, Scutari G 2016. Distributed nonconvex optimization over time-varying networks. 2016 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 16)4124–28 New York: IEEE
     [Google Scholar]
  84. 84.  Di Lorenzo P, Scutari G 2016. NEXT: in-network nonconvex optimization. IEEE Trans. Signal Inf. Process. Netw. 2:120–36
     [Google Scholar]
  85. 85.  Tatarenko T, Touri B 2016. Non-convex distributed optimization. arXiv1512.00895
  86. 86.  Nedić A, Olshevsky A, Shi W 2016. Achieving geometric convergence for distributed optimization over time-varying graphs. IEEE Trans. Autom. Control 62:3744–57
     [Google Scholar]
  87. 87.  Nedić A, Olshevsky A, Shi W, Uribe C 2017. Geometrically convergent distributed optimization with uncoordinated step-sizes. 2017 American Control Conference (ACC)3950–55 New York: IEEE
     [Google Scholar]
  88. 88.  Yang T, Lu J, Wu D, Wu J, Shi G et al. 2017. A distributed algorithm for economic dispatch over time-varying directed networks with delays. IEEE Trans. Ind. Electron. 64:5095–106
     [Google Scholar]
  89. 89.  Kar S, Hug G 2012. Distributed robust economic dispatch in power systems: a consensus + innovations approach. 2012 IEEE Power and Energy Society General Meeting New York: IEEE https://doi.org/10.1109/PESGM.2012.6345156
    [Crossref] [Google Scholar]
  90. 90.  Dominguez-Garcia A, Cady S, Hadjicostis CN 2012. Decentralized optimal dispatch of distributed energy resources. 2012 IEEE 51st Annual Conference on Decision and Control (CDC)3688–93 New York: IEEE
     [Google Scholar]
  91. 91.  Yang S, Tan S, Xu JX 2013. Consensus based approach for economic dispatch problem in a smart grid. IEEE Trans. Power Syst. 28:4416–26
     [Google Scholar]
  92. 92.  Xing H, Mou Y, Fu M, Lin Z 2015. Distributed bisection method for economic power dispatch in smart grid. IEEE Trans. Power Syst. 30:3024–35
     [Google Scholar]
  93. 93.  Zhao C, Topcu U, Low SH 2013. Optimal load control via frequency measurement and neighborhood area communication. IEEE Trans. Power Syst. 28:3576–87
     [Google Scholar]
  94. 94.  Yi P, Hong Y, Liu F 2015. Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Syst. Control Lett. 83:45–52
     [Google Scholar]
  95. 95.  Zhang W, Liu W, Wang X, Liu L, Ferrese F 2013. Online optimal generation control based on constrained distributed gradient algorithm. IEEE Trans. Power Syst. 30:35–45
     [Google Scholar]
  96. 96.  Zhao C, He J, Cheng P, Chen J 2016. Consensus-based energy management in smart grid with transmission losses and directed communication. IEEE Trans. Smart Grid 8:2049–61
     [Google Scholar]
  97. 97.  Xiao L, Boyd S 2006. Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl. 129:469–88
     [Google Scholar]
  98. 98.  Nabavi S, Zhang J, Chakrabortty A 2015. Distributed optimization algorithms for wide-area oscillation monitoring in power systems using interregional PMU-PDC architectures. IEEE Trans. Smart Grid 6:2529–38
     [Google Scholar]
  99. 99.  Summers TH, Lygeros J 2012. Distributed model predictive consensus via the alternating direction method of multipliers. 2012 50th Annual Allerton Conference on Communication, Control, and Computing79–84 New York: IEEE
     [Google Scholar]
  100. 100.  Conte C, Summers TH, Zeilinger MN, Morari M, Jones CN 2012. Computational aspects of distributed optimization in model predictive control. 2012 IEEE 51st Annual Conference on Decision and Control (CDC)6819–24 New York: IEEE
     [Google Scholar]
  101. 101.  Mota JFC, Xavier JMF, Aguiar PMQ, Püschel M 2015. Distributed optimization with local domains: applications in MPC and network flows. IEEE Trans. Autom. Control 60:2004–09
     [Google Scholar]
  102. 102.  Christofides PD, Scattolini R, de la Peña DM, Liu J 2013. Distributed model predictive control: a tutorial review and future research directions. Comput. Chem. Eng. 51:21–41
     [Google Scholar]
/content/journals/10.1146/annurev-control-060117-105131
Loading
  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error