Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Relaxed hybrid consensus ADMM for distributed convex optimisation with coupling constraints

© The Institution of Engineering and Technology
Received 30/10/2018, Accepted 07/06/2019, Revised 27/03/2019, Published 13/06/2019

In this study, the solution of a convex distributed optimisation problem with a global coupling inequality constraint is considered. By using the Lagrange duality framework, the problem is transformed into a distributed consensus optimisation problem and then based on the recently proposed Hybrid Alternating Direction Method of Multipliers (H-ADMM), which merges distributed and centralised optimisation concepts problems, a novel distributed algorithm is developed. In particular, the authors offer a reformulation of the original H-ADMM in an operator theoretical framework, which exploits the known relationship between ADMM and Douglas–Rachford splitting. In addition, the authors' formulation allows us to generalise the H-ADMM by including a relaxation constant, not present in the original design of the algorithm. Moreover, an adaptive penalty parameter selection scheme that consistently improves the practical convergence properties of the algorithm is proposed. Finally, the convergence results of the proposed algorithm are discussed and moreover, in order to present the effectiveness and the major capabilities of the proposed algorithm in off-line and on-line scenarios, distributed quadratic programming and distributed model predictive control problems are considered in the simulation section.

Inspec keywords: convex programming; convergence of numerical methods; predictive control; distributed control; gradient methods; iterative methods; convergence; distributed algorithms; quadratic programming

Other keywords: hybrid alternating direction method; distributed quadratic programming; distributed consensus optimisation problem; distributed algorithm; convex distributed optimisation problem; Lagrange duality framework; coupling constraints; global coupling inequality constraint; distributed convex optimisation; relaxed hybrid consensus ADMM; centralised optimisation concepts problems; distributed model predictive control problems; hybrid alternating direction method of multipliers; Douglas–Rachford splitting; operator theoretical framework; original H-ADMM; adaptive penalty parameter selection scheme

Subjects: Multivariable control systems; Optimisation techniques; Optimal control

References

    1. 1)
      • 28. Iutzeler, F., Bianchi, P., Ciblat, P., et al: ‘Explicit convergence rate of a distributed alternating direction method of multipliers’, IEEE Trans. Autom. Control, 2016, 61, (4), pp. 892–904.
    2. 2)
      • 21. Glowinski, R., Marroco, A.: ‘Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires’, Revue française d'automatique, informatique, recherche opérationnelle Analyse numérique, 1975, 9, (R2), pp. 41–76.
    3. 3)
      • 2. Bertsekas, D.P., Scientific, A.: ‘Convex optimization algorithms’ (Athena Scientific, Belmont, 2015).
    4. 4)
      • 16. Farina, F., Garulli, A., Giannitrapani, A., et al: ‘A distributed asynchronous method of multipliers for constrained nonconvex optimization’, Automatica, 2019, 103, pp. 243–253. Available at: https://linkinghub.elsevier.com/retrieve/pii/S0005109819300469.
    5. 5)
      • 43. Wang, Z., Ong, C.J.: ‘Accelerated distributed mpc of linear discrete-time systems with coupled constraints’, IEEE Trans. Autom. Control, 2018, 63, pp. 3838–3849.
    6. 6)
      • 8. Slavakis, K., Giannakis, G.B., Mateos, G.: ‘Modeling and optimization for big data analytics:(statistical) learning tools for our era of data deluge’, IEEE Signal Process. Mag., 2014, 31, (5), pp. 18–31.
    7. 7)
      • 17. Chang, T.H.: ‘A proximal dual consensus ADMM method for multi-aAgent constrained optimization’, IEEE Trans. Signal Process., 2016, 64, (14), pp. 3719–3734.
    8. 8)
      • 31. Ghadimi, E., Teixeira, A., Shames, I., et al: ‘Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems’, IEEE Trans. Autom. Control, 2015, 60, (3), pp. 644–658.
    9. 9)
      • 27. Wei, E., Ozdaglar, A: ‘On the o(1/k) convergence of asynchronous distributed alternating direction method of multipliers’. IEEE Global Conf. on Signal and Information Processing (GlobalSIP 2013), Austin, USA, 2013, pp. 551–554.
    10. 10)
      • 33. Xu, Z., Figueiredo, M.A., Yuan, X., et al: ‘Adaptive relaxed admm: convergence theory and practical implementation’. IEEE 2017 IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Honolulu, USA, 2017, pp. 7234–7243.
    11. 11)
      • 35. Xu, Z., Taylor, G., Li, H., et al: ‘Adaptive consensus ADMM for distributed optimization’, 2017, arXiv preprint arXiv:170602869.
    12. 12)
      • 34. Song, C., Yoon, S., Pavlovic, V: ‘Fast admm algorithm for distributed optimization with adaptive penalty’. Association for the Advancement of Artificial Intelligence (AAAI), Phoenix, USA, 2016, pp. 753–759.
    13. 13)
      • 7. Boyd, S., Parikh, N., Chu, E., et al: ‘Distributed optimization and statistical learning via the alternating direction method of multipliers’, Found. Trends® Mach. Learn., 2011, 3, (1), pp. 1–122.
    14. 14)
      • 11. Yıldırım, K.S., Carli, R., Schenato, L., et al: ‘A distributed dual-ascent approach for power control of wireless power transfer networks’. IEEE 56th Annual Conf. on Decision and Control (CDC 2017), Melbourne, Australia, 2017, pp. 3507–3512.
    15. 15)
      • 14. Wang, R., Li, Q., Zhang, B., et al: ‘Distributed consensus based algorithm for economic dispatch in a microgrid’, IEEE Trans. Smart Grid, 2018, 10, pp. 935–945.
    16. 16)
      • 1. Nedić, A., Liu, J.: ‘Distributed optimization for control’, Annu. Rev. Control Robot. Auton. Syst., 2018, 1, pp. 77–103.
    17. 17)
      • 29. Peng, Z., Xu, Y., Yan, M., et al: ‘Arock: an algorithmic framework for asynchronous parallel coordinate updates’, SIAM J. Sci. Comput., 2016, 38, (5), pp. A2851–A2879.
    18. 18)
      • 10. Bolognani, S., Carli, R., Todescato, M: ‘State estimation in power distribution networks with poorly synchronized measurements’. IEEE 53rd Annual Conf. on Decision and Control (CDC 2014), Los Angeles, USA, 2014, pp. 2579–2584.
    19. 19)
      • 37. Bauschke, H.H., Combettes, P.L.: ‘Convex analysis and monotone operator theory in Hilbert spaces’ (Springer, New York, 2017).
    20. 20)
      • 38. Davis, D., Yin, W.: ‘Faster convergence rates of relaxed peaceman-rachford and admm under regularity assumptions’, Math. Oper. Res., 2017, 42, (3), pp. 783–805.
    21. 21)
      • 5. Necoara, I., Suykens, J.: ‘Interior-point lagrangian decomposition method for separable convex optimization’, J. Optim. Theory Appl., 2009, 143, (3), p. 567.
    22. 22)
      • 22. Gabay, D., Mercier, B.: ‘A dual algorithm for the solution of non linear variational problems via finite element approximation’ (Institut de recherche d'informatique et d'automatique, Rocquencourt, 1975).
    23. 23)
      • 30. Ma, M., Nikolakopoulos, A.N., Giannakis, G.B.: ‘Fast decentralized optimization over networks’, 2018, arXiv preprint arXiv:180402425.
    24. 24)
      • 3. He, B., Hou, L., Yuan, X.: ‘On full jacobian decomposition of the augmented lagrangian method for separable convex programming’, SIAM J. Optim., 2015, 25, (4), pp. 2274–2312.
    25. 25)
      • 9. Dall'Anese, E., Simonetto, A.: ‘Optimal power flow pursuit’, IEEE Trans. Smart Grid, 2018, 9, (2), pp. 942–952.
    26. 26)
      • 18. Notarnicola, I., Sun, Y., Scutari, G., et al: ‘Distributed big-data optimization via block-iterative convexification and averaging’. 2017 IEEE 56th Annual Conf. on Decision and Control (CDC), Melbourne, Australia, 2017, pp. 2281–2288.
    27. 27)
      • 36. Ryu, E.K., Boyd, S.: ‘Primer on monotone operator methods’, Appl. Comput. Math., 2016, 15, (1), pp. 3–43.
    28. 28)
      • 12. Lewis, F.L.: ‘Wireless sensor networks’ in Cook, D.J., Das, S.K. (Eds.): ‘Smart environments: technologies, protocols, and applications’ (Wiley, Hoboken, 2004), pp. 11–46.
    29. 29)
      • 25. Hong, M.: ‘A distributed, asynchronous and incremental algorithm for nonconvex optimization: an admm approach’, IEEE Trans. Control Netw. Syst., 2017, 5, pp. 3630–3640.
    30. 30)
      • 4. Chang, X., Liu, S., Zhao, P., et al: ‘Convergent prediction–correction-based admm for multi-block separable convex programming’, J. Comput. Appl. Math., 2018, 335, pp. 270–288.
    31. 31)
      • 23. Eckstein, J., Yao, W.: ‘Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives’, Pacific J. Optim., 2015, 11, (4), pp. 619–644.
    32. 32)
      • 42. Camponogara, E., Scherer, H.F.: ‘Distributed optimization for model predictive control of linear dynamic networks with control-input and output constraints’, IEEE Trans. Autom. Sci. Eng., 2011, 8, (1), pp. 233–242.
    33. 33)
      • 24. Zhang, R., Kwok, J: ‘Asynchronous distributed admm for consensus optimization’. Int. Conf. on Machine Learning, Beijing, China, 2014, pp. 1701–1709.
    34. 34)
      • 32. Giselsson, P., Boyd, S.: ‘Linear convergence and metric selection for douglas-rachford splitting and admm’, IEEE Trans. Autom. Control, 2017, 62, (2), pp. 532–544.
    35. 35)
      • 40. Nedić, A., Olshevsky, A.: ‘Distributed optimization over time-varying directed graphs’, IEEE Trans. Autom. Control, 2015, 60, (3), pp. 601–615.
    36. 36)
      • 15. Wang, Z., Ong, C.J.: ‘Distributed model predictive control of linear discrete-time systems with local and global constraints’, Automatica, 2017, 81, pp. 184–195.
    37. 37)
      • 6. Bai, J., Zhang, H., Li, J.: ‘A parameterized proximal point algorithm for separable convex optimization’, Optim. Lett., 2018, 12, (7), pp. 1589–1608.
    38. 38)
      • 41. Scherer, H., Camponogara, E., Normey-Rico, J.: , et al‘Distributed mpc for resource-constrained control systems’, Optim. Control Appl. Methods, 2015, 36, (3), pp. 272–291.
    39. 39)
      • 20. Xie, P., You, K., Tempo, R., et al: ‘Distributed convex optimization with inequality constraints over time-Varying unbalanced digraphs’, IEEE Trans. Autom. Control, 2018, 63, (12), pp. 4331–4337.
    40. 40)
      • 19. Chen, G., Yang, Q.: ‘Distributed constrained optimization for multi-agent networks with nonsmooth objective functions’, Syst. Control Lett., 2019, 124, pp. 60–67. Available at: https://linkinghub.elsevier.com/retrieve/pii/S0167691118302226.
    41. 41)
      • 26. Mota, J.F.C., Xavier, J.M.F., Aguiar, P.M.Q., et al: ‘D-admm: A communication-efficient distributed algorithm for separable optimization’, IEEE Trans. Signal Process., 2013, 61, (10), pp. 2718–2723.
    42. 42)
      • 13. Carron, A., Todescato, M., Carli, R., et al: ‘An asynchronous consensus-based algorithm for estimation from noisy relative measurements’, IEEE Trans. Control Netw. Syst., 2014, 1, (3), pp. 283–295.
    43. 43)
      • 39. Giselsson, P., Boyd, S: ‘Diagonal scaling in douglas-rachford splitting and admm’. 2014 IEEE 53rd Annual Conf. on Decision and Control (CDC), 2014, pp. 5033–5039.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta.2018.6260
Loading

Related content

content/journals/10.1049/iet-cta.2018.6260
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address